Submission #35757

#TimeUsernameProblemLanguageResultExecution timeMemory
35757funcsrICC (CEOI16_icc)C++14
100 / 100
126 ms2224 KiB
#include "icc.h" #include <iostream> #include <vector> #include <tuple> #include <algorithm> #include <set> #include <cassert> #define rep(i, n) for (int i=0; i<(n); i++) #define pb push_back #define all(x) x.begin(), x.end() using namespace std; int query(vector<int> a, vector<int> b) { if (a.empty() || b.empty()) return 0; int ar[100] = {}, br[100] = {}; rep(i, a.size()) ar[i] = a[i]+1; rep(i, b.size()) br[i] = b[i]+1; return query(a.size(), b.size(), ar, br); } int N; int U[100], id[100]; vector<int> R[100]; int find(int x) { if (U[x] == x) return x; return U[x] = find(U[x]); } void unite(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (R[x].size() < R[y].size()) swap(x, y); U[y] = x; for (int t : R[y]) R[x].pb(t); R[y].clear(); } vector<int> roots() { vector<int> ret; rep(i, N) if (find(i) == i) { id[i] = ret.size(); ret.pb(i); } return ret; } int find(vector<int> X, vector<int> other) { if (X.size() == 1) return X[0]; vector<int> a, b; rep(i, X.size()) { if (i&1) b.pb(X[i]); else a.pb(X[i]); } if (query(a, other)) return find(a, other); else return find(b, other); } void run(int n) { N = n; rep(i, N) U[i] = i, R[i].pb(i); rep(_, N-1) { vector<int> a, b; vector<int> vs = roots(); int n = vs.size(); int XOR = 0; pair<vector<int>, vector<int>> ps; for (int e=0; (1<<e)<n; e++) { vector<int> Sa, Sb; rep(i, n) { if ((i>>e)&1) for (int x : R[vs[i]]) Sa.pb(x); else for (int x : R[vs[i]]) Sb.pb(x); } if (query(Sa, Sb)) { XOR ^= 1<<e; swap(a, Sa); swap(b, Sb); } } assert(!a.empty()); int u = find(a, b); //int v = find(b, a); int v = find(R[vs[id[find(u)]^XOR]], a); //assert((id[find(u)]^id[find(v)]) == XOR); unite(u, v); setRoad(u+1, v+1); } }

Compilation message (stderr)

icc.cpp: In function 'int query(std::vector<int>, std::vector<int>)':
icc.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
icc.cpp:17:3: note: in expansion of macro 'rep'
   rep(i, a.size()) ar[i] = a[i]+1;
   ^
icc.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
icc.cpp:18:3: note: in expansion of macro 'rep'
   rep(i, b.size()) br[i] = b[i]+1;
   ^
icc.cpp: In function 'int find(std::vector<int>, std::vector<int>)':
icc.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
icc.cpp:47:3: note: in expansion of macro 'rep'
   rep(i, X.size()) {
   ^
#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...