Submission #293150

#TimeUsernameProblemLanguageResultExecution timeMemory
293150Leonardo16Split the Attractions (IOI19_split)C++14
40 / 100
161 ms23792 KiB
/// Code by Leonardo16 /// “Your focus determines your reality.” – Qui-Gon Jinn #include<bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //#pragma GCC option("arch=native","tune=native","no-zero-upper") //#pragma GCC target("avx2") //#define int long long #define ll long long #define sz size #define ull unsigned long long #define ld long double #define ii pair<int,int> #define fst first #define scd second #define vi vector<int> #define vii vector<ii> #define pb push_back #define pf push_front #define fl '\n' #define el endl #define all(x) x.begin() , x.end() #define rall(x) x.rbegin() , x.rend() /// Functions #define db(x) cerr << #x << ": " << (x) << '\n'; #define random() __builtin_ia32_rdtsc() #define lg2(x) 31-__builtin_clz(x) #define lg2ll(x) 63-__builtin_clzll(x) #define pi acos(-1) #define YN(x) cout<<((x)?("YES"):("NO"))<<fl; #define yn(x) cout<<((x)?("Yes"):("No"))<<fl; #define des(x,s1,s2,end1,end2) cout<<((x)?(s1):(s2))<<fl;if(x){end1;}else{end2;} #define precision(x) cout.setf(ios::fixed);cout.precision(x); /// Red-Black Tree Template //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //using namespace __gnu_pbds; //typedef tree < long long , null_type , less<long long> , rb_tree_tag , tree_order_statistics_node_update > ordered_set; //#define less_than(n) order_of_key(n) //#define en_pos(n) find_by_order(n) /// Prime numbers 173,179,311,331,737,1009,2011,2027,3079,4001,100003 ///===================================================================== vi g[200005]; bool mk[200005]; int n,a,b,c; int dp[200005]; bool found=false; bool mk2[200005]; vi vb,va,vc; void dfb(int u){ if(vb.sz()<b)vb.pb(u); else return; mk2[u]=true; for(auto v:g[u]){ if(mk2[v])continue; dfb(v); } } void dfa(int u){ if(va.sz()<a)va.pb(u); else return; mk2[u]=true; for(auto v:g[u]){ if(mk2[v])continue; dfa(v); } } void dfc(int u){ if(vc.sz()<c)vc.pb(u); else return; mk2[u]=true; for(auto v:g[u]){ if(mk2[v])continue; dfc(v); } } void dfsab(int u){ mk[u]=true; dp[u]=1; int p=-1; for(auto v:g[u]){ if(mk[v]){p=v;continue;} dfsab(v); dp[u]+=dp[v]; } if(!found ){ if( dp[u]>=a && n-dp[u]>=b ){ found=true; mk2[u]=1; dfb(p); va.pb(u); for(auto v:g[u]){ if(v!=p){ dfa(v); } } return; } if( dp[u]>=a && n-dp[u]>=c ){ found=true; mk2[u]=1; dfc(p); va.pb(u); for(auto v:g[u]){ if(v!=p){ dfa(v); } } return; } if( dp[u]>=b && n-dp[u]>=c ){ found=true; mk2[u]=1; dfc(p); vb.pb(u); for(auto v:g[u]){ if(v!=p){ dfb(v); } } return; } if( dp[u]>=b && n-dp[u]>=a ){ found=true; mk2[u]=1; dfa(p); vb.pb(u); for(auto v:g[u]){ if(v!=p){ dfb(v); } } return; } if( dp[u]>=c && n-dp[u]>=a ){ found=true; mk2[u]=1; dfa(p); vc.pb(u); for(auto v:g[u]){ if(v!=p){ dfc(v); } } return; } if( dp[u]>=c && n-dp[u]>=b ){ found=true; mk2[u]=1; dfb(p); vc.pb(u); for(auto v:g[u]){ if(v!=p){ dfc(v); } } return; } } } vi find_split(int nn,int aa,int bb,int cc,vi p,vi q){ n=nn;a=aa;b=bb;c=cc; vi sol; for(int i=0;i<n;i++){ sol.pb(0); } for(int i=0;i<p.sz();i++){ g[p[i]].pb(q[i]); g[q[i]].pb(p[i]); } dfsab(0); if(va.sz()>0 || vb.sz()>0 ){ map<int,int>mp; mp[1]++;mp[2]++;mp[3]++; for(auto it:va){ sol[it]=1; mp.erase(1); } for(auto it:vb){ sol[it]=2; mp.erase(2); } for(auto it:vc){ sol[it]=3; mp.erase(3); } int rem=0; for(auto it:mp){ rem=it.fst; } for(int i=0;i<n;i++){ if(sol[i]==0){ sol[i]=rem; } } return sol; } return sol; } //main(){ // find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5}); // //}

Compilation message (stderr)

split.cpp: In function 'void dfb(int)':
split.cpp:55:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     if(vb.sz()<b)vb.pb(u);
      |        ~~~~~~~^~
split.cpp: In function 'void dfa(int)':
split.cpp:66:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     if(va.sz()<a)va.pb(u);
      |        ~~~~~~~^~
split.cpp: In function 'void dfc(int)':
split.cpp:77:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |     if(vc.sz()<c)vc.pb(u);
      |        ~~~~~~~^~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:199:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |     for(int i=0;i<p.sz();i++){
      |                 ~^~~~~~~
#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...