Submission #1187354

#TimeUsernameProblemLanguageResultExecution timeMemory
11873548pete8The Ties That Guide Us (CEOI23_incursion)C++20
0 / 100
59 ms5656 KiB
#include<bits/stdc++.h> #include "incursion.h" using namespace std; #define f first #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-lopps") #define sz(x) (int)((x).size()) const int mxn=5e4; vector<int>adj[mxn]; int sz[mxn],target,val[mxn],pa[mxn],n; int root[mxn]; void getsz(int cur,int p){ sz[cur]=1;for(auto i:adj[cur])if(i!=p&&root[i]==0){ pa[i]=cur; getsz(i,cur),sz[cur]+=sz[i]; } } vector<int>have; bool find(int cur,int p){ val[cur]=0; if(cur==target)return val[cur]=1; for(auto i:adj[cur])if(i!=p&&root[i]==0){ val[cur]|=find(i,cur); } return val[cur]; } void getroot(){ getsz(1,-1); for(int i=1;i<=n;i++){ int yes=1; for(auto j:adj[i])if(j!=pa[i])yes&=(sz[j]<=(n)/2); if(i!=1)yes&=((sz[1]-sz[i])<=((n)/2)); if(yes)have.pb(i); } if(have.size()>2||have.empty())assert(0); for(auto i:have)root[i]=1; for(auto i:have)find(i,-1); } vector<int> mark(vector<pii>F, int safe){ n=F.size()+1; have.clear(); for(int i=1;i<=n;i++)adj[i].clear(),val[i]=root[i]=0; for(auto i:F){ adj[i.f].pb(i.s); adj[i.s].pb(i.f); } target=safe; getroot(); vector<int>ans; for(int i=1;i<=n;i++)ans.pb(val[i]); return ans; } void locate(vector<pii>F, int curr, int t){ n=F.size()+1; int cur=curr; have.clear(); for(int i=1;i<=n;i++)adj[i].clear(),val[i]=root[i]=0; for(auto i:F){ adj[i.f].pb(i.s); adj[i.s].pb(i.f); } for(int i=1;i<=n;i++)if(adj[i].empty())assert(0); getroot(); for(auto i:have)getsz(i,-1); if(have.size()>1)pa[have[0]]=have[1],pa[have[1]]=have[0]; while(t==0){ cur=pa[cur]; if(cur==0)assert(0); t=visit(cur); } if(cur==0||t==0)assert(0); vector<int>choice; while(1){ choice.clear(); for(auto i:adj[cur]){ if(i!=pa[cur])choice.pb(i); } if(choice.size()>1&&sz[choice[0]]<sz[choice[1]]){ swap(choice[0],choice[1]); } if(choice.empty())return; t=visit(choice[0]); if(t){ cur=choice[0]; } else{ visit(cur); if(choice.size()>1&&(!visit(choice[1])))return void(visit(cur)); cur=choice[1]; } } }

Compilation message (stderr)

incursion.cpp:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   16 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
incursion.cpp:22:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   22 | void getsz(int cur,int p){
      |                         ^
incursion.cpp:29:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   29 | bool find(int cur,int p){
      |                        ^
incursion.cpp:37:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   37 | void getroot(){
      |              ^
incursion.cpp:50:40: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   50 | vector<int> mark(vector<pii>F, int safe){
      |                                        ^
incursion.cpp:64:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   64 | void locate(vector<pii>F, int curr, int t){
      |                                          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...