Submission #619737

#TimeUsernameProblemLanguageResultExecution timeMemory
619737Sergio_2357Simurgh (IOI17_simurgh)C++17
0 / 100
1 ms212 KiB
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; struct DSU { vi v, sz; int cg; int find(int x) { if (v[x] == -1) return x; v[x] = find(v[x]); return v[x]; } void join(int a, int b) { a = find(a); b = find(b); if (a == b) return; cg--; if (sz[a] > sz[b]) swap(a, b); v[a] = b; sz[b] += sz[a]; } DSU(int n) { v = vi(n + 10, -1); sz = vi(n + 10, 1); cg = n; } }; bool test(vi u, vi v) { DSU dsu(u.size()); for (int i = 0; i < u.size(); i++) dsu.join(u[i], v[i]); return dsu.cg == 1; } vi to_list(int b) { vi r; for (int i = 0; i < 25; i++) { if (b & (1ll << i)) r.push_back(i); } return r; } vi find_roads(int n, vi u, vi v) { //cout << "HELLO" << endl; for (int b = 0; b < (1ll << (u.size())); b++) { vi tu, tv; vi lst = to_list(b); for (int x : lst) { tu.push_back(u[x]); tv.push_back(v[x]); } if (tu.size() == n - 1 && test(tu, tv) && (count_common_roads(lst) == n - 1)) return lst; } return to_list((1ll << (n - 1)) - 1); }

Compilation message (stderr)

simurgh.cpp: In function 'bool test(vi, vi)':
simurgh.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < u.size(); i++)
      |                     ~~^~~~~~~~~~
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:66:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |         if (tu.size() == n - 1 && test(tu, tv) && (count_common_roads(lst) == n - 1))
      |             ~~~~~~~~~~^~~~~~~~
#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...