Submission #619728

#TimeUsernameProblemLanguageResultExecution timeMemory
619728Sergio_2357Simurgh (IOI17_simurgh)C++17
0 / 100
1 ms340 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, -1); sz = vi(n, 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() - 1)); b++) { vi tu, tv; for (int x : to_list(b)) { tu.push_back(u[x]); tv.push_back(v[x]); } //for (int x : to_list(b)) // cout << x << ' '; //cout << endl; if (tu.size() == n - 1 && test(tu, tv) && (count_common_roads(to_list(b)) == n - 1)) { //cout << "HERE" << endl; return to_list(b); } else { //cout << "Not here" << endl; } } //cout << "Not found" << endl; 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:68:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |         if (tu.size() == n - 1 && test(tu, tv) && (count_common_roads(to_list(b)) == n - 1)) {
      |             ~~~~~~~~~~^~~~~~~~
simurgh.cpp:76:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   76 |     return to_list((1ll << n - 1) - 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...