Submission #1012954

#TimeUsernameProblemLanguageResultExecution timeMemory
1012954CookieCollapse (JOI18_collapse)C++14
100 / 100
4633 ms235040 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; //#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx2,tune=native") //huhu #define sz(a) (int)a.size() #define ALL(v) v.begin(), v.end() #define ALLR(v) v.rbegin(), v.rend() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> #define mpp make_pair #define ull unsigned long long const int mxn = 1e5 + 5, inf = 1e9 + 5, sq = 350; #include "collapse.h" int n; struct DSU{ int pa[mxn + 1]; vt<int>comp; void init(){ for(int i = 0; i < n; i++)pa[i] = -1; } int fp(int u){ if(pa[u] < 0)return(u); return(pa[u] = fp(pa[u])); } bool unon(int u, int v){ comp.pb(u); comp.pb(v); u = fp(u); v = fp(v); if(u == v)return(0); if(-pa[u] < -pa[v])swap(u, v); pa[u] += pa[v]; pa[v] = u; return(1); } void reset(){ for(auto i: comp){ pa[i] = -1; } comp.clear(); } }; struct Q{ int tme, p, id; bool operator <(const Q &other){ return(p < other.p); } }; vt<Q>queries; bool cmpl(pii a, pii b){ return(a.se < b.se); } bool cmpr(pii a, pii b){ return(a.fi > b.fi); } vt<int>t, x, y, w, p, res; set<pair<int, int>>all; // edges after block[i - 1] vt<pii>inblock[mxn + 1]; // edges that appear in block void solve(int l, int r){ set<pair<int, int>>remain = all; for(int i = l; i <= r; i++){ if(t[i] == 1 && remain.count(mpp(x[i], y[i]))){ remain.erase(mpp(x[i], y[i])); } } map<pair<int, int>, int>last; for(int i = l; i <= r; i++){ if(t[i] == 0){ assert(last.find(mpp(x[i], y[i])) == last.end()); last[mpp(x[i], y[i])] = i; }else{ int lt = ((last.find(mpp(x[i], y[i])) == last.end()) ? l : last[mpp(x[i], y[i])]); for(int j = lt; j < i; j++){ inblock[j].pb(mpp(x[i], y[i])); } last.erase(mpp(x[i], y[i])); } } for(auto i: last){ for(int j = i.se; j <= r; j++){ inblock[j].pb(i.fi); } } vt<pii>edge; for(auto i: remain)edge.pb(i); sort(ALL(edge), cmpl); vt<Q>curr; for(auto i: queries){ if(i.tme >= l && i.tme <= r){ curr.pb({i.tme, i.p, i.id}); } } sort(ALL(curr)); int lp = 0; DSU dsu, dsu2; dsu.init(); dsu2.init(); int cnt = 0; //global connection for(auto [tme, pl, id]: curr){ while(lp < sz(edge) && edge[lp].se <= pl){ cnt += dsu.unon(edge[lp].fi, edge[lp].se); lp++; } int cnt2 = cnt; // connection for this query only for(auto [u, v]: inblock[tme]){ if(v <= pl){ cnt2 += dsu2.unon(dsu.fp(u), dsu.fp(v)); } } dsu2.reset(); res[id] += (pl) - cnt2; } dsu.init(); dsu2.init(); curr.clear(); // same thing but for right side :> for(auto i: queries){ if(i.tme >= l && i.tme <= r){ curr.pb({i.tme, i.p + 1, i.id}); } } sort(ALLR(curr)); sort(ALL(edge), cmpr); int rp = 0; cnt = 0; //global connection for(auto [tme, pr, id]: curr){ while(rp < sz(edge) && edge[rp].fi >= pr){ cnt += dsu.unon(edge[rp].fi, edge[rp].se); rp++; } int cnt2 = cnt; // connection for this query only for(auto [u, v]: inblock[tme]){ if(u >= pr){ cnt2 += dsu2.unon(dsu.fp(u), dsu.fp(v)); } } dsu2.reset(); res[id] += (n - pr + 1) - cnt2; } for(int i = l; i <= r; i++){ if(t[i] == 0)all.insert(mpp(x[i], y[i])); else all.erase(mpp(x[i], y[i])); } } std::vector<int> simulateCollapse( int N, std::vector<int> T, std::vector<int> X, std::vector<int> Y, std::vector<int> W, std::vector<int> P ) { n = N; t = T; x = X; y = Y; w = W; p = P; for(int i = 0; i < sz(x); i++){ if(x[i] > y[i])swap(x[i], y[i]); } for(int i = 0; i < sz(w); i++){ queries.pb({w[i], p[i], i}); } res.resize(sz(queries)); int l = 0; for(int i = 0; i < sz(t); i += sq){ solve(i, min(i + sq - 1, sz(t) - 1)); } return(res); } /* int main(int argc, char *argv[]) { int N, C, Q; 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); } } */

Compilation message (stderr)

collapse.cpp: In function 'void solve(int, int)':
collapse.cpp:108:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |     for(auto [tme, pl, id]: curr){
      |              ^
collapse.cpp:113:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |         for(auto [u, v]: inblock[tme]){
      |                  ^
collapse.cpp:133:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  133 |     for(auto [tme, pr, id]: curr){
      |              ^
collapse.cpp:138:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |         for(auto [u, v]: inblock[tme]){
      |                  ^
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:169:6: warning: unused variable 'l' [-Wunused-variable]
  169 |  int l = 0;
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...