제출 #400089

#제출 시각아이디문제언어결과실행 시간메모리
400089luisgalan슈퍼트리 잇기 (IOI20_supertrees)C++14
46 / 100
363 ms23916 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << (x) << endl const int MAX_N = 1e3 + 3; int find(int x, vector<int> &ufds) { return ufds[x] = (ufds[x] == x ? x : find(ufds[x], ufds)); } void connect(int a, int b, vector<int> &ufds) { if (rand() % 2) swap(a, b); ufds[find(a, ufds)] = find(b, ufds); } int construct(std::vector<std::vector<int>> p) { int n = p.size(); vector<vector<int>> result(n); fill(result.begin(), result.end(), vector<int>(n)); if (n == 1) { build(result); return 1; } vector<int> trees(n); vector<int> components(n); for (int i = 0; i < n; i++) { trees[i] = i; components[i] = i; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (p[i][j] == 1) { connect(i, j, trees); } if (p[i][j] > 0) { connect(i, j, components); } } } for (int i = 0; i < n; i++) { cerr << find(i, trees) << ", "; } cerr << endl; for (int i = 0; i < n; i++) { cerr << find(i, components) << ", "; } cerr << endl; for (int i = 0; i < n; i++) { int a = find(i, trees); if (i == a) continue; result[i][a] = 1; result[a][i] = 1; } vector<vector<int>> cycles(n); set<int> visited; for (int i = 0; i < n; i++) { int t = find(i, trees); int c = find(i, components); if (!visited.count(t)) { cycles[c].push_back(t); visited.insert(t); } } for (int i = 0; i < n; i++) { vector<int> &cycle = cycles[i]; for (int j = 0; j < cycle.size(); j++) { int a = cycle[j]; int b = cycle[(j + 1) % cycle.size()]; if (a == b) continue; result[a][b] = 1; result[b][a] = 1; } } build(result); return 1; } // it's easy to prove that there must be at most one cycle for st5 (and that any matrix with some p[i][j] = 2 must have a cycle) // but we could have more than one tree // we essentially have that some nodes are part of the cycle and then we have multiple trees rooted in one of the cycle nodes // we could have nodes 1 2 3 and 4 where p[1][2] = 1, p[3][4] = 1 but p[2][3] = 2 // we have that p[i][j] = 2 iff the paths go through the cycle // we essentially have a collection of trees // if p[i][j] = 2 then node i and j must be on the same component but of different trees // if p[i][j] = 1 then node i and j belong to the same tree // it doesn't actually matter which node we root the tree in (ie which node we put on the cycle) // we thus have the following algorithm: // if p[i][j] = 1 connect them in the tree ufds // if p[i][j] > 0 connect them in the component ufds // for each node A in the same component connect find(A) to the cycle

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int j = 0; j < cycle.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...