제출 #742573

#제출 시각아이디문제언어결과실행 시간메모리
742573myrcellaSplit the Attractions (IOI19_split)C++17
22 / 100
525 ms1048576 KiB
//by szh #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pii pair<int,int> #define pll pair<long long,long long> #define pb push_back #define debug(x) cerr<<#x<<"="<<x<<endl #define pq priority_queue #define inf 0x3f #define rep(i,a,b) for (int i=a;i<(b);i++) #define MP make_pair #define SZ(x) (int(x.size())) #define ll long long #define mod 1000000007 #define ALL(x) x.begin(),x.end() void inc(int &a,int b) {a=(a+b)%mod;} void dec(int &a,int b) {a=(a-b+mod)%mod;} int lowbit(int x) {return x&(-x);} ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;} #include "split.h" const int maxn = 2e5+10; vector <int> res; vector <int> edge[maxn]; bool vis[maxn]; int sz[maxn],fa[maxn]; void dfs(int u,int lst) { sz[u] = 1; fa[u] = lst; for (int v:edge[u]) { if (v==lst) continue; dfs(v,u); sz[u] += sz[v]; } return; } int rest; void solve(int u,int val) { if (rest==0) return; vis[u] = 1; res[u] = val; rest--; for (int v:edge[u]) { if (v==fa[u] or vis[v]) continue; solve(v,val); } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { rep(i,0,SZ(p)) edge[p[i]].pb(q[i]),edge[q[i]].pb(p[i]); res.resize(n); rep(i,0,n) res[i] = 0; dfs(0,-1); int tmp[3] = {a,b,c}; rep(i,0,n) { // debug(sz[i]); rep(j,0,3) rep(k,0,3) if (k!=j and sz[i]>=tmp[j] and n-sz[i]>=tmp[k]) { rest=tmp[j],solve(i,j+1); //debug(i),debug(j),debug(rest); rest=tmp[k],solve(0,k+1); rep(t,0,n) if (res[t]==0) res[t] = 3-j-k+1; return res; } } return res; }
#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...