Submission #558771

#TimeUsernameProblemLanguageResultExecution timeMemory
558771TrunktyAmusement Park (JOI17_amusement_park)C++14
18 / 100
32 ms6540 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define DEBUG #ifdef DEBUG #define debug(x) cout << #x << ": " << x << endl #else #define debug(x) #endif #include "Joi.h" vector<int> roads[10005],tree[10005]; ll siz[100005],pos[100005],dia,pa,pb; bool check[10005]; void dfs(int x){ check[x] = true; siz[x] = 1; pos[x] = x; for(int i:roads[x]){ if(!check[i]){ tree[x].push_back(i); tree[i].push_back(x); dfs(i); if(siz[x]+siz[i]>dia){ pa = pos[x]; pb = pos[i]; dia = max(dia,siz[x]+siz[i]); } if(siz[i]+1>siz[x]){ siz[x] = siz[i]+1; pos[x] = pos[i]; } } } } ll dep[100005],par[100005]; void one(int x, int p, ll d){ par[x] = p; dep[x] = d; for(int i:tree[x]){ if(i!=p){ one(i,x,d+1); } } } ll nextnode,xx; void two(int x, int p){ if(nextnode<60){ if((1LL<<nextnode)&xx){ MessageBoard(x,1); } else{ MessageBoard(x,0); } nextnode++; } else{ MessageBoard(x,0); } for(int i:tree[x]){ if(i!=p){ two(i,x); } } } void Joi(int n, int m, int a[], int b[], ll x, int t){ xx = x; for(int i=0;i<m;i++){ roads[a[i]].push_back(b[i]); roads[b[i]].push_back(a[i]); } dfs(0); if(dia>=60){ one(pa,-1,0); for(int i=0;i<n;i++){ if((1LL<<(dep[i]%60LL))&x){ MessageBoard(i,1); } else{ MessageBoard(i,0); } } } else{ one(0,-1,0); dia/=2; if(dep[pb]>dep[pa]){ swap(pa,pb); } for(int i=1;i<=dia;i++){ pa = par[pa]; } one(pa,-1,0); two(pa,-1); return; } }
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define DEBUG #ifdef DEBUG #define debug(x) cout << #x << ": " << x << endl #else #define debug(x) #endif #include "Ioi.h" vector<int> roads[10005],tree[10005]; ll siz[100005],pos[100005],dia,pa,pb; bool check[10005]; void dfs(int x){ check[x] = true; siz[x] = 1; pos[x] = x; for(int i:roads[x]){ if(!check[i]){ tree[x].push_back(i); tree[i].push_back(x); dfs(i); if(siz[x]+siz[i]>dia){ pa = pos[x]; pb = pos[i]; dia = max(dia,siz[x]+siz[i]); } if(siz[i]+1>siz[x]){ siz[x] = siz[i]+1; pos[x] = pos[i]; } } } } ll dep[100005],par[100005]; void one(int x, int p, ll d){ par[x] = p; dep[x] = d; for(int i:tree[x]){ if(i!=p){ one(i,x,d+1); } } } ll ans=0,typ[100005],nextnode; void two(int x, int p){ if(nextnode<60){ typ[x] = nextnode; nextnode++; } else{ typ[x] = -1; } for(int i:tree[x]){ if(i!=p){ two(i,x); } } } int s; void three(int x, int p){ s++; vector<vector<ll>> ord; for(int i:tree[x]){ if(i!=p and typ[i]!=-1){ ord.push_back({typ[i],i}); } } sort(ord.begin(),ord.end(),greater<vector<ll>>()); for(vector<ll> i:ord){ if(Move(i[1])){ ans += (1LL<<(typ[i[1]])); } three(i[1],x); } if(s!=60){ Move(p); } } ll Ioi(int n, int m, int a[], int b[], int p, int v, int t){ for(int i=0;i<m;i++){ roads[a[i]].push_back(b[i]); roads[b[i]].push_back(a[i]); } dfs(0); if(dia>=60){ one(pa,-1,0); if(dep[p]<=60){ if(p!=pa){ while(par[p]!=pa){ Move(par[p]); p = par[p]; } p = par[p]; if(Move(p)){ ans += (1LL<<(dep[p]%60LL)); } } else{ if(v){ ans += (1LL<<(dep[p]%60LL)); } } for(int i=1;i<=59;i++){ for(int x:tree[p]){ if(dep[x]==i){ p = x; if(Move(p)){ ans += (1LL<<(dep[p]%60LL)); } break; } } } } else{ if(v){ ans += (1LL<<(dep[p]%60LL)); } for(int i=1;i<=59;i++){ p = par[p]; if(Move(p)){ ans += (1LL<<(dep[p]%60LL)); } } } } else{ one(0,-1,0); dia/=2; if(dep[pb]>dep[pa]){ swap(pa,pb); } for(int i=1;i<=dia;i++){ pa = par[pa]; } one(pa,-1,0); if(p!=pa){ while(par[p]!=pa){ Move(par[p]); p = par[p]; } p = par[p]; if(Move(p)){ ans += (1LL<<(0LL%60LL)); } } else{ if(v){ ans += (1LL<<(0LL%60LL)); } } two(pa,-1); three(pa,-1); } return ans; }
#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...