제출 #523996

#제출 시각아이디문제언어결과실행 시간메모리
523996keertanRegions (IOI09_regions)C++17
60 / 100
1965 ms115736 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> using namespace std; //#define int int64_t #define rep(Begin,End) for (Begin=0;Begin<(End);Begin++) #define all(x) x.begin(), x.end() #define all1(x) x.rbegin(), x.rend() #define sz(x) (int32_t)(x.size()) const int64_t N = 3e5+4, mod =998244353; const int64_t N1=1e18; const double eps=1e-6,cmp=1e-3; int tin[N],tout[N],c[N]; int tmr=1; vector<int> adj[N]; vector<int> ctin[N],ctout[N],col[N]; int stnd[N],ennd[N]; void dfs(int u,int v){ tin[u]=tmr; stnd[tmr]=u; //cerr<<u<< " "<<c[u]<<"\n"; ctin[c[u]].push_back(tmr++); col[c[u]].push_back(u); for (const int& it:adj[u]){ if (it==v){continue;} dfs(it,u); } tout[u]=tmr; ennd[tmr++]=u; ctout[c[u]].push_back(tout[u]); } int child(int p,int chld){ int ans=0; //cerr<<"chld"; for (const int& it:col[chld]){ //cerr<<it<<" "; int cur=0,cur1=0; for (int lg=(1ll<<18);lg;lg>>=1){ if (sz(ctin[p])>=cur+lg && ctin[p][cur+lg-1]<tin[it]){ cur+=lg; } if (sz(ctout[p])>=cur1+lg && ctout[p][cur1+lg-1]<=tin[it]){ cur1+=lg; } } //cerr<<cur<<" "<<cur1; ans+=cur-cur1; } return ans; } int parent(int p,int chld){ int ans=0; //cerr<<"gh"; //cout<<tin[1]<<" "<<tout[1]<<"\n"; for (const int& it:col[p]){ //cerr<<it<<" "; int cur=0,cur1=0; for (int lg=(1ll<<18);lg;lg>>=1){ if (sz(ctin[chld])>=cur+lg && ctin[chld][cur+lg-1]<=tin[it]){ cur+=lg; } if (sz(ctin[chld])>=cur1+lg && ctin[chld][cur1+lg-1]<=tout[it]){ cur1+=lg; } } // cerr<<cur<<" "<<cur1<<"\n"; ans+=cur1-cur; } return ans; } void solve(){ int n,r,q; cin>>n>>r>>q; cin>>c[1]; for (int i=2,x,p;i<=n;i++){ cin>>p>>x; c[i]=x; adj[p].push_back(i); } dfs(1,1); map<pair<int,int>,int> mp; for (int r,r1;q;q--){ cin>>r>>r1; if (mp.find({r,r1})!=mp.end()){cout<<mp[{r,r1}]<<endl;continue;} int ans=0; if (sz(col[r])<sz(col[r1])){ ans=parent(r,r1); } else{ // cerr<<"fck\n"; ans=child(r,r1); } mp[{r,r1}]=ans; cout<<ans<<endl; } } int32_t main(){ ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr); int tq = 1; //cin>>tq; for (;tq;tq--){solve();} }

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

regions.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...