제출 #654109

#제출 시각아이디문제언어결과실행 시간메모리
654109kymInside information (BOI21_servers)C++14
50 / 100
370 ms100912 KiB
#include <bits/stdc++.h> using namespace std; #define int ll #define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i) #define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i) #define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL #define db(x) cerr << #x << "=" << x << "\n" #define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n" #define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n" #define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n" #define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n" #define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n" #else #define db(x) #define db2(x,y) #define db3(a,b,c) #define dbv(v) #define dbvp(v) #define dba(a,ss,ee) #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define ll long long #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define f first #define s second #define g0(x) get<0>(x) #define g1(x) get<1>(x) #define g2(x) get<2>(x) #define g3(x) get<3>(x) #define reach cerr << "LINE: " << __LINE__ << "\n"; typedef pair <ll, ll> pi; typedef tuple<ll,ll,ll> ti3; typedef tuple<ll,ll,ll,ll> ti4; ll rand(ll a, ll b) { return a + rng() % (b-a+1); } const int MOD = 1e9 + 7; const int inf = (int)1e9 + 500; const long long oo = (ll)1e18 + 500; template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; } template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; } const int MAXN = 120005; int n; int k; vector<pi> V[MAXN]; vector<ti3> queries; int twok[MAXN][20]; bool inc[MAXN][20]; bool decr[MAXN][20]; int depth[MAXN]; int W[MAXN]; int lst[MAXN][20]; int dp[MAXN]; int out[MAXN]; int st[MAXN], en[MAXN]; int cnt=1; void predfs(int x, int p, int lvl, int w) { st[x]=cnt++; depth[x]=lvl; twok[x][0]=p; lst[x][0]=w; inc[x][0]=1; decr[x][0]=1; FOR(i,1,19) { if(twok[x][i-1]==-1)break; twok[x][i]=twok[twok[x][i-1]][i-1]; lst[x][i]=lst[twok[x][i-1]][i-1]; inc[x][i]=(inc[twok[x][i-1]][i-1]) & (inc[x][i-1]) & ((twok[x][i-1]!=1)?(lst[x][i-1] < W[ twok[x][i-1]]):1); decr[x][i]=(decr[twok[x][i-1]][i-1]) & (decr[x][i-1]) & ((twok[x][i-1]!=1)?(lst[x][i-1] > W[ twok[x][i-1]]):1); } for(auto v:V[x])if(v.f!=p) { W[v.f]=v.s; predfs(v.f,x,lvl+1,v.s); } en[x]=cnt-1; } int kth_parent(int x, int k){ for (int i = 0; i <= 19; i++){ if (k & (1 << i)) x = twok[x][i]; if (x <= -1) return -1; } return x; } int prex=0, prey=inf; bool checkinc(int x, int k) { bool r=1; int pre=0; for (int i = 0; i <= 19; i++){ if (k & (1 << i)) { chmin(r, (W[x] > pre)); chmin(r,inc[x][i]); pre = lst[x][i]; prex=lst[x][i]; x = twok[x][i]; } if (x <= -1) return r; } return r; } bool checkdec(int x, int k) { bool r=1; int pre=inf; for (int i = 0; i <= 19; i++){ if (k & (1 << i)) { chmin(r, (W[x] < pre)); chmin(r,decr[x][i]); pre = lst[x][i]; prey=lst[x][i]; x = twok[x][i]; } if (x <= -1) return r; } return r; } bool lca(int x, int y){ // is edge weight increasing from x->y? bool r=1; prex=0,prey=inf; if (depth[x] > depth[y]) { int dd = depth[x] - depth[y]; // reach chmin(r, checkinc(x,dd)); if(!r)return 0; x = kth_parent(x, dd); } else { int dd = depth[y] - depth[x]; //reach chmin(r,checkdec(y,dd)); if(!r)return 0; y = kth_parent(y, dd); } if (x == y) return r; for (int i = 19; i >= 0; i--){ if (twok[x][i] != twok[y][i]){ //x = twok[x][i]; chmin(r, (W[x]>prex)); chmin(r,inc[x][i]); prex=lst[x][i]; x=twok[x][i]; //y = twok[y][i]; chmin(r, (W[y]<prey)); chmin(r, decr[y][i]); prey=lst[y][i]; y=twok[y][i]; if(r==0)return 0; } } chmin(r, (W[x]>prex)); chmin(r, (W[y]<prey)); chmin(r, (W[x]<W[y])); return r; } struct ufds_ { int p[MAXN]; ufds_() { iota(p,p+MAXN,0); } int find(int x) { if(x==p[x])return x; else return p[x]=find(p[x]); } void merge(int x, int y) { x=find(x); y=find(y); p[y]=x; } bool same(int x, int y) { x=find(x); y=find(y); return (x==y); } } ufds; int dp_inc[MAXN]; int dp_dec[MAXN]; vector<pi> events[MAXN]; vector<pi> nodequeries[MAXN]; vector<pi> thisnode[MAXN]; map<pi,int> mp; int fw[MAXN]; void update(int x, int v) { // DO NOT call this function even for point update here! for (; x<MAXN; x+=x&(-x)) fw[x] += v; } void update(int x, int y, int v){ update(x, v); update(y + 1, -v); } int sum(int x) { int res = 0; for(; x; x-=x&(-x)) res += fw[x]; return res; } void dfs1(int x, int p) { sort(all(V[x]), [](pi x, pi y) { return W[x.f]>W[y.f]; }); dbvp(V[x]); if(x!=1) { if(W[x] > W[p]){ dp_inc[x]=p; dp_dec[x]=dp_dec[p]; } else { dp_dec[x]=p; dp_inc[x]=dp_inc[p]; } } else { dp_inc[x]=dp_dec[x]=0; } for(auto v:V[x])if(v.f!=p) { dfs1(v.f,x); } } void dfs2(int x, int p) { db2(x,p); update(max(W[x],1ll),MAXN-1,1); events[dp_dec[x]].pb(pi(W[x],-1)); sort(all(nodequeries[x]), [](pi x, pi y) { return st[x.f]>st[y.f]; }); dbvp(nodequeries[x]); while(nodequeries[x].size()) { pi c=nodequeries[x].back(); db3(x,c.f,c.s); if(st[V[x][0].f]<=st[c.f] && st[c.f] <= en[V[x][0].f]){ db3(x,c.s,sum(c.s)); mp[pi(x, c.s)] = sum(c.s); nodequeries[x].pop_back(); } else { break; } } for(int i=0;i<(int)V[x].size();i++){ if(V[x][i].f==p) continue; dfs2(V[x][i].f,x); if(i<V[x].size()-1) { db(x); while(nodequeries[x].size()) { pi c=nodequeries[x].back(); db3(x,c.f,c.s); if(st[V[x][i+1].f]<=st[c.f] && st[c.f] <= en[V[x][i+1].f]){ db3(x,c.s,sum(c.s)); mp[pi(x, c.s)] = sum(c.s); nodequeries[x].pop_back(); } else { break; } } } } while(thisnode[x].size()) { pi c=thisnode[x].back(); mp[pi(x,c.s)]=sum(c.s); thisnode[x].pop_back(); } for(auto i:events[x]) { update(max(1ll,i.f),MAXN-1,i.s); } } int32_t main() { IAMSPEED memset(twok,-1,sizeof twok); cin >> n >> k; FOR(i,1,n)dp[i]=1; int q=n+k-1; FOR(i,1,q) { char op; cin >> op; if(op == 'S') { int a,b; cin >> a >> b; queries.pb(ti3(op,a,b)); } else if(op=='Q') { int a,b; cin >> a >> b; queries.pb(ti3(op,a,b)); } else { int d; cin >> d; queries.pb(ti3(op,d,-1)); } } int t=0; for(auto x:queries) { ++t; char op=g0(x); if(op == 'S') { int a=g1(x); int b=g2(x); V[a].pb(pi(b,t)); V[b].pb(pi(a,t)); } } predfs(1,-1,0,0); dfs1(1,-1); int idx=0; for(auto qq:queries) { ++idx; char op=g0(qq); if(op=='S') { int a=g1(qq); int b=g2(qq); ufds.merge(a,b); } else if(op == 'Q') { int a, d; a=g1(qq); d=g2(qq); if(ufds.same(a,d) == 0){ out[idx]=0; continue; } if(lca(d,a)) { out[idx]=1; } else { out[idx]=0; } } else { int x=g1(qq); thisnode[x].pb(pi(x,idx)); if(dp_inc[x]!=1)nodequeries[twok[dp_inc[x]][0]].pb(pi(x,idx)); db2(x,twok[dp_inc[x]][0]); } } /* solve the C queries */ dfs2(1,-1); reach idx=0; for(auto qq:queries) { ++idx; char op=g0(qq); if(op=='S') { } else if(op == 'Q') { if(out[idx]==1)cout<<"yes\n"; else cout << "no\n"; } else { int x=g1(qq); db2(dp_inc[x],idx); db2(mp[pi(twok[dp_inc[x]][0],idx)], mp[pi(x,idx)]); if(dp_inc[x] != 0)cout << mp[pi(x,idx)] - mp[pi(twok[dp_inc[x]][0],idx)] << '\n'; else cout << mp[pi(x,idx)] << '\n'; } } }

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

servers.cpp: In function 'void dfs2(long long int, long long int)':
servers.cpp:244:7: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  244 |   if(i<V[x].size()-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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...