Submission #141092

#TimeUsernameProblemLanguageResultExecution timeMemory
141092baboKey of Impassable Doors (FXCUP3_key)C++14
0 / 100
1061 ms760 KiB
#include "key.h" #include <bits/stdc++.h> #define va first #define vb second using namespace std; using pii = pair<int,int>; int par[1005]; vector<int> cyc[1005], P[1005]; int sz[1005]; int n_cyc, clk; int cycid[1005]; int chk[1005]; int gsz(int i){ TakeKey(i); return Explore(); } int gsz_range(int s, int e, vector<int>& T, int u){ for(int i = s; i <= e; i++) TakeKey(T[i]); TakeKey(u); int K = Explore(); //cout << "gsz_range = " << K << '\n'; return K; } int get_union(int s, int e, vector<int>& T, int lim){ ++clk; int cnt = 0; for(int i = s; i <= e && i < lim; i++){ int t = T[i]; while(true){ if(!par[t]){ if(chk[t] == clk) break; for(int u : cyc[ cycid[t] ]){ chk[u] = clk; ++cnt; } break; } if(chk[t] == clk) break; chk[t] = clk; ++cnt; t = par[t]; } } for(int i = lim; i <= e; i++) cnt += sz[ T[i] ]; //cout << "get_union = " << cnt << '\n'; return cnt; } void Report_tree(int s, int t){ while(par[t]){ Report(s, t); t = par[t]; } for(int u : cyc[cycid[t]]) Report(s, u); } void Report_cycle(vector<int>& C){ for(int u : C){ for(int v : C){ if(u != v) Report(u, v); } } } void EnsureKeyInfo(int n) { for(int i = 1; i <= n; i++){ int g = gsz(i); P[g].push_back(i); sz[i] = g; Report(i, i); } for(int u : P[1]){ cycid[u] = ++n_cyc; cyc[n_cyc].push_back(u); } for(int j = 2; j <= n; j++){ int s_cyc = n_cyc + 1; //cout << "j = " << j << '\n'; int capt = P[j-1].size(); for(int u : P[j]){ //cout << "u = " << u << '\n'; int lo = 0, hi = (int)P[j-1].size()-1, mi; //cout << "P : "; for(int k : P[j-1]) cout << k << ' '; cout << '\n'; if(gsz_range(lo, hi, P[j-1], u) == get_union(lo, hi, P[j-1], capt) + j){ //cout << "making new cycle\n"; P[j-1].push_back(u); cycid[u] = ++n_cyc; cyc[n_cyc].push_back(u); continue; } while(lo < hi){ mi = lo + hi >> 1; if(gsz_range(lo, mi, P[j-1], u) > get_union(lo, mi, P[j-1], capt) + 1) lo = mi + 1; else hi = mi; } //cout << "bs result : " << P[j-1][lo] << '\n'; if(lo < capt){ par[u] = P[j-1][lo]; Report_tree(u, P[j-1][lo]); } else{ cycid[u] = cycid[ P[j-1][lo] ]; cyc[cycid[ P[j-1][lo] ]].push_back(u); } } for(int i = s_cyc; i <= n_cyc; i++){ if(cyc[i].size() != j) while(1); Report_cycle(cyc[i]); } //cout << '\n'; } }

Compilation message (stderr)

key.cpp: In function 'void EnsureKeyInfo(int)':
key.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mi = lo + hi >> 1;
          ~~~^~~~
key.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(cyc[i].size() != j) while(1);
       ~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...