제출 #202908

#제출 시각아이디문제언어결과실행 시간메모리
202908MercenaryCollapse (JOI18_collapse)C++14
35 / 100
4777 ms26760 KiB
#ifndef LOCAL #include "collapse.h" #endif // LOCAL #include<bits/stdc++.h> #define pb push_back #define mp make_pair using namespace std; const int maxn = 1e5 + 5; typedef pair<int,int> ii; int n , m , q; vector<int> Q[maxn]; int type[maxn] , x[maxn] , y[maxn]; int p[maxn] , w[maxn]; int in[maxn] , out[maxn]; int res[maxn]; struct Dsurollback{ vector<pair<int*,int>> data; int lab[maxn]; int FindLab(int u){ return lab[u] < 0 ? u : FindLab(lab[u]); } void Change(int & u , int v){ data.pb(mp(&u,u)); u = v; } void rollback(int sz){ while(data.size() > sz){ (*data.back().first) = data.back().second; data.pop_back(); } cnt -= cnt1; cnt1 = 0; } int cnt = 0; int cnt1 = 0; void Merge(int u , int v){ u = FindLab(u);v = FindLab(v); if(u == v)return; if(lab[u] > lab[v])swap(u,v); Change(lab[u],lab[u]+lab[v]); Change(lab[v],u); cnt++;cnt1++; } int cur(){return cnt1 = 0 , data.size();}; void reset(){ fill_n(lab,maxn,-1);cnt = cnt1 = 0; data.clear(); } }Dsu; void solve(){ const int MAGIC = 400; for(int l = 0 ; l < m ; l += MAGIC){ vector<int> sp , norm,q; int r = min(m,l+MAGIC) - 1; for(int i = 0 ; i <= r ; ++i){ if(i >= l)for(auto & id : Q[i])q.pb(id); if(out[i] < l || type[i] == 1)continue; if(i < l && out[i] > r)norm.pb(i); else sp.pb(i); } sort(norm.begin(),norm.end(),[&](const int a , const int b){return y[a] < y[b];}); sort(q.begin(),q.end(),[&](const int a , const int b){return p[a] < p[b];}); int qi = 0 , qe = 0; Dsu.reset(); for(int i = 0 ; i < n ; ++i){ while(qe < norm.size() && y[norm[qe]] == i)Dsu.Merge(x[norm[qe]] , y[norm[qe]]),++qe; int tmp = Dsu.cnt; while(qi < q.size() && p[q[qi]] == i){ int id = q[qi]; int pre = Dsu.cur(); for(auto & c : sp){ if(y[c] <= i && c <= w[id] && w[id] < out[c])Dsu.Merge(x[c],y[c]); } res[id] -= Dsu.cnt; Dsu.rollback(pre); ++qi; } } // cerr << norm.size() << " " << Dsu.cnt << endl; sort(norm.begin(),norm.end(),[&](const int a , const int b){return x[a] > x[b];}); reverse(q.begin(),q.end()); qi = 0 , qe = 0; Dsu.reset(); for(int i = n - 1 ; i >= 0 ; --i){ while(qe < norm.size() && x[norm[qe]] == i){ Dsu.Merge(x[norm[qe]] , y[norm[qe]]),++qe; } while(qi < q.size() && p[q[qi]] == i - 1){ int id = q[qi]; int pre = Dsu.cur(); for(auto & c : sp){ if(x[c] >= i && c <= w[id] && w[id] < out[c]){ Dsu.Merge(x[c],y[c]); } } res[id] -= Dsu.cnt; Dsu.rollback(pre); ++qi; } } } } vector<int> simulateCollapse(int N,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) { n = N;m = T.size();q = W.size(); for(int i = 0 ; i < m ; ++i){ type[i] = T[i]; x[i] = X[i];y[i] = Y[i]; if(x[i] > y[i])swap(x[i],y[i]); } for(int i = 0 ; i < q ; ++i){ p[i] = P[i];w[i] = W[i]; Q[w[i]].pb(i); } map<ii,int> mmap; for(int i = 0 ; i < m ; ++i){ if(type[i] == 0){ mmap[mp(x[i],y[i])] = i; }else{ out[mmap[mp(x[i],y[i])]] = i; } } for(int i = 0 ; i < m ; ++i)if(type[i] == 0 && out[i] == 0)out[i] = m; solve(); vector<int> res; for(int i = 0 ; i < q ; ++i)res.pb(::res[i] + n); return res; } #ifdef LOCAL int main(int argc, char *argv[]) { int N, C, Q; freopen("A.INP","r",stdin); freopen("A.OUT","w",stdout); scanf("%d%d%d", &N, &C, &Q); std::vector<int> T(C), X(C), Y(C); for(int i = 0; i < C; i++) { scanf("%d%d%d", &T[i], &X[i], &Y[i]); } std::vector<int> W(Q), P(Q); for(int i = 0; i < Q; i++) { scanf("%d%d", &W[i], &P[i]); } auto res = simulateCollapse(N, T, X, Y, W, P); for(auto i : res) { printf("%d\n", i); } } #endif

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

collapse.cpp: In member function 'void Dsurollback::rollback(int)':
collapse.cpp:30:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(data.size() > sz){
               ~~~~~~~~~~~~^~~~
collapse.cpp: In function 'void solve()':
collapse.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qe < norm.size() && y[norm[qe]] == i)Dsu.Merge(x[norm[qe]] , y[norm[qe]]),++qe;
                   ~~~^~~~~~~~~~~~~
collapse.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qi < q.size() && p[q[qi]] == i){
                   ~~~^~~~~~~~~~
collapse.cpp:71:17: warning: unused variable 'tmp' [-Wunused-variable]
             int tmp = Dsu.cnt;
                 ^~~
collapse.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qe < norm.size() && x[norm[qe]] == i){
                   ~~~^~~~~~~~~~~~~
collapse.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qi < q.size() && p[q[qi]] == i - 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...