第2回早稲田大学プログラミングコンテスト

Submission #1454784

Source codeソースコード

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
/*
 * Union-Find tree
 * header requirement: vector
 */
class UnionFind {
private:
  std::vector<int> disj;
  std::vector<int> rank;
public:
  UnionFind(int n) : disj(n), rank(n) {
    for (int i = 0; i < n; ++i) {
      disj[i] = i;
      rank[i] = 0;
    }
  }
  int root(int x) {
    if (disj[x] == x) {
      return x;
    }
    return disj[x] = root(disj[x]);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return;
    }
    if (rank[x] < rank[y]) {
      disj[x] = y;
    } else {
      disj[y] = x;
      if (rank[x] == rank[y]) {
	++rank[x];
      }
    }
  }
  bool is_same_set(int x, int y) {
    return root(x) == root(y);
  }
};

const int N = 123;
vector<PI> edges[N];
int n, m, k;

pair<vector<VI>, int> get_cycle_bfs(void) {
  // add all vertices of degree 1
  queue<int> degone;
  vector<vector<int> > ecp(n, VI(n, -1));
  VI deg(n);
  REP(i, 0, n) {
    REP(j, 0, edges[i].size()) {
      ecp[i][edges[i][j].first] = j;
      deg[i] += 1;
    }
  }
  REP(i, 0, n) {
    if (deg[i] == 1) {
      degone.push(i);
    }
  }
  while (not degone.empty()) {
    int t = degone.front(); degone.pop();
    int u = -1;
    REP(i, 0, n) {
      if (ecp[t][i] >= 0) {
	u = i;
      }
    }
    if (u < 0) { continue; }
    ecp[t][u] = -1;
    ecp[u][t] = -1;
    deg[t] -= 1;
    deg[u] -= 1;
    if (deg[u] == 1) {
      degone.push(u);
    }
  }
  // There should remain a single cycle
  int start = -1;
  REP(i, 0, n) {
    if (deg[i] >= 0) {
      start = i;
    }
  }
  return make_pair(ecp, start);
}


int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> k;
  UnionFind uf(n);
  int conn = n;
  vector<PI> cs;
  // Assume graph is a tree
  REP(i, 0, m) {
    int f, t, c;
    cin >> f >> t >> c;
    f--, t--;
    edges[f].push_back(PI(t, c));
    edges[t].push_back(PI(f, c));
    if (not uf.is_same_set(f, t)) {
      conn--;
    }
    uf.unite(f, t);
  }
  pair<vector<VI>, int> cycle_start = get_cycle_bfs();
  vector<VI> cycle = cycle_start.first;
  vector<set<int> > cycle_dir(n);
  VI testa;
  REP(i, 0, n) {
    REP(j, 0, n) {
      if (cycle[i][j] < 0) { continue; }
      int d = edges[i][cycle[i][j]].second;
      cycle_dir[i].insert(j);
      cycle_dir[j].insert(i);
      testa.push_back(d);
    }
  }
  REP(i, 0, n) {
    REP(j, 0, edges[i].size()) {
      PI wd = edges[i][j];
      int w = wd.first;
      int d = wd.second;
      if (cycle_dir[i].count(w)) { continue; }
      if (i < w) {
	cs.push_back(PI(d, 0));
      }
    }
  }
  sort(testa.begin(), testa.end());
  if (testa.size() >= 1) {
    assert (testa.size() >= 3);
    cs.push_back(PI(testa[0] + testa[1], -1));
  }
  sort(cs.rbegin(), cs.rend());
  int tot = 0;
  REP(i, 0, k - conn) {
    PI c = cs.back();
    cs.pop_back();
    tot += c.first;
    if (c.second == -1) {
      // pushing
      REP(j, 2, testa.size()) {
	cs.push_back(PI(testa[j], 0));
      }
      sort(cs.rbegin(), cs.rend());
    }
  }
  cout << tot << "\n";
}

Submission

Task問題 E - 独立記念日
User nameユーザ名 koba@チーム戦の時は別垢を作れ!
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 30
Source lengthソースコード長 3778 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
nonloop 30 / 30 nonloop/case_000.txt,nonloop/case_001.txt,nonloop/case_002.txt,nonloop/case_003.txt,nonloop/case_004.txt,nonloop/case_005.txt,nonloop/case_006.txt,nonloop/case_007.txt,nonloop/case_008.txt,nonloop/case_009.txt,nonloop/case_010.txt,nonloop/case_011.txt,nonloop/case_012.txt,nonloop/case_013.txt,nonloop/case_014.txt,nonloop/case_015.txt,nonloop/case_016.txt,nonloop/case_017.txt,nonloop/case_018.txt,nonloop/case_019.txt,nonloop/case_020.txt,nonloop/case_021.txt,nonloop/case_022.txt,nonloop/case_023.txt,nonloop/case_024.txt,nonloop/case_025.txt,nonloop/case_026.txt,nonloop/case_027.txt,nonloop/case_028.txt,nonloop/case_029.txt,nonloop/case_030.txt,nonloop/case_031.txt,nonloop/case_032.txt,nonloop/case_033.txt
loop 0 / 70 loop/case_000.txt,loop/case_001.txt,loop/case_002.txt,loop/case_003.txt,loop/case_004.txt,loop/case_005.txt,loop/case_006.txt,loop/case_007.txt,loop/case_008.txt,loop/case_009.txt,loop/case_010.txt,loop/case_011.txt,loop/case_012.txt,loop/case_013.txt,loop/case_014.txt,loop/case_015.txt,loop/case_016.txt,loop/case_017.txt,loop/case_018.txt,loop/case_019.txt,loop/case_020.txt,loop/case_021.txt,loop/case_022.txt,loop/case_023.txt,loop/case_024.txt,loop/case_025.txt,loop/case_026.txt,loop/case_027.txt,loop/case_028.txt,loop/case_029.txt,loop/case_030.txt,loop/case_031.txt,loop/case_032.txt,loop/case_033.txt,loop/loop_case_000.txt,loop/loop_case_001.txt,loop/loop_case_002.txt,loop/loop_case_003.txt,loop/loop_case_004.txt,loop/loop_case_005.txt,loop/loop_case_006.txt,loop/loop_case_007.txt,loop/loop_case_008.txt,loop/loop_case_009.txt,loop/loop_case_010.txt,loop/loop_case_011.txt,loop/loop_case_012.txt,loop/loop_case_013.txt,loop/loop_case_014.txt,loop/loop_case_015.txt,loop/loop_case_016.txt,loop/loop_case_017.txt,loop/loop_case_018.txt,loop/loop_case_019.txt,loop/loop_case_020.txt,loop/loop_case_021.txt,loop/loop_case_022.txt,loop/loop_case_023.txt,loop/loop_case_024.txt,loop/loop_case_025.txt,loop/loop_case_026.txt,loop/loop_case_027.txt,loop/loop_case_028.txt,loop/loop_case_029.txt,loop/loop_case_030.txt,loop/loop_case_031.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
loop/case_000.txt AC 1 ms 256 KB
loop/case_001.txt AC 1 ms 256 KB
loop/case_002.txt AC 1 ms 256 KB
loop/case_003.txt AC 1 ms 256 KB
loop/case_004.txt AC 1 ms 256 KB
loop/case_005.txt AC 1 ms 256 KB
loop/case_006.txt AC 1 ms 256 KB
loop/case_007.txt AC 1 ms 384 KB
loop/case_008.txt AC 1 ms 384 KB
loop/case_009.txt AC 1 ms 384 KB
loop/case_010.txt AC 1 ms 256 KB
loop/case_011.txt AC 1 ms 256 KB
loop/case_012.txt AC 1 ms 256 KB
loop/case_013.txt AC 1 ms 256 KB
loop/case_014.txt AC 1 ms 384 KB
loop/case_015.txt AC 1 ms 384 KB
loop/case_016.txt AC 1 ms 256 KB
loop/case_017.txt AC 1 ms 256 KB
loop/case_018.txt AC 1 ms 384 KB
loop/case_019.txt AC 1 ms 256 KB
loop/case_020.txt AC 1 ms 256 KB
loop/case_021.txt AC 1 ms 256 KB
loop/case_022.txt AC 1 ms 256 KB
loop/case_023.txt AC 1 ms 384 KB
loop/case_024.txt AC 1 ms 256 KB
loop/case_025.txt AC 1 ms 256 KB
loop/case_026.txt AC 1 ms 384 KB
loop/case_027.txt AC 1 ms 256 KB
loop/case_028.txt AC 1 ms 256 KB
loop/case_029.txt AC 1 ms 256 KB
loop/case_030.txt AC 1 ms 256 KB
loop/case_031.txt AC 1 ms 384 KB
loop/case_032.txt AC 1 ms 384 KB
loop/case_033.txt AC 1 ms 384 KB
loop/loop_case_000.txt AC 1 ms 256 KB
loop/loop_case_001.txt WA
loop/loop_case_002.txt WA
loop/loop_case_003.txt AC 1 ms 256 KB
loop/loop_case_004.txt WA
loop/loop_case_005.txt WA
loop/loop_case_006.txt AC 1 ms 256 KB
loop/loop_case_007.txt WA
loop/loop_case_008.txt AC 1 ms 256 KB
loop/loop_case_009.txt AC 1 ms 256 KB
loop/loop_case_010.txt AC 1 ms 256 KB
loop/loop_case_011.txt WA
loop/loop_case_012.txt AC 1 ms 256 KB
loop/loop_case_013.txt AC 1 ms 384 KB
loop/loop_case_014.txt AC 1 ms 256 KB
loop/loop_case_015.txt AC 1 ms 256 KB
loop/loop_case_016.txt AC 1 ms 256 KB
loop/loop_case_017.txt AC 1 ms 384 KB
loop/loop_case_018.txt AC 1 ms 384 KB
loop/loop_case_019.txt AC 1 ms 256 KB
loop/loop_case_020.txt WA
loop/loop_case_021.txt AC 1 ms 256 KB
loop/loop_case_022.txt AC 1 ms 384 KB
loop/loop_case_023.txt AC 1 ms 384 KB
loop/loop_case_024.txt WA
loop/loop_case_025.txt AC 1 ms 256 KB
loop/loop_case_026.txt AC 1 ms 256 KB
loop/loop_case_027.txt AC 1 ms 384 KB
loop/loop_case_028.txt WA
loop/loop_case_029.txt AC 1 ms 384 KB
loop/loop_case_030.txt WA
loop/loop_case_031.txt AC 1 ms 256 KB
nonloop/case_000.txt AC 1 ms 256 KB
nonloop/case_001.txt AC 1 ms 256 KB
nonloop/case_002.txt AC 1 ms 256 KB
nonloop/case_003.txt AC 1 ms 256 KB
nonloop/case_004.txt AC 1 ms 256 KB
nonloop/case_005.txt AC 1 ms 256 KB
nonloop/case_006.txt AC 1 ms 256 KB
nonloop/case_007.txt AC 1 ms 384 KB
nonloop/case_008.txt AC 1 ms 384 KB
nonloop/case_009.txt AC 1 ms 384 KB
nonloop/case_010.txt AC 1 ms 256 KB
nonloop/case_011.txt AC 1 ms 256 KB
nonloop/case_012.txt AC 1 ms 256 KB
nonloop/case_013.txt AC 1 ms 256 KB
nonloop/case_014.txt AC 1 ms 384 KB
nonloop/case_015.txt AC 1 ms 384 KB
nonloop/case_016.txt AC 1 ms 256 KB
nonloop/case_017.txt AC 1 ms 256 KB
nonloop/case_018.txt AC 1 ms 384 KB
nonloop/case_019.txt AC 1 ms 256 KB
nonloop/case_020.txt AC 1 ms 256 KB
nonloop/case_021.txt AC 1 ms 256 KB
nonloop/case_022.txt AC 1 ms 256 KB
nonloop/case_023.txt AC 1 ms 384 KB
nonloop/case_024.txt AC 1 ms 256 KB
nonloop/case_025.txt AC 1 ms 256 KB
nonloop/case_026.txt AC 1 ms 384 KB
nonloop/case_027.txt AC 1 ms 256 KB
nonloop/case_028.txt AC 1 ms 256 KB
nonloop/case_029.txt AC 1 ms 256 KB
nonloop/case_030.txt AC 1 ms 256 KB
nonloop/case_031.txt AC 1 ms 384 KB
nonloop/case_032.txt AC 1 ms 384 KB
nonloop/case_033.txt AC 1 ms 384 KB