| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1174277 | mertbbm | Amusement Park (JOI17_amusement_park) | C++20 | 0 ms | 0 KiB |
struct DSU{
vector<int>e;
void init(int n){
e=vector<int>(n,-1);
}
int get(int x){
return e[x]<0?x:e[x]=get(e[x]);
}
bool unite(int x, int y){
x=get(x); y=get(y);
if(x==y) return 0;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y];
e[y]=x;
return 1;
}
};
vector<int>adj2[10005];
int in2[10005];
int ptr2=-1;
vector<int>storage2[65];
void dfs3(int index, int par){
in2[index]=++ptr2;
storage2[in2[index]%60].push_back(index);
for(auto it:adj2[index]){
if(it==par) continue;
dfs3(it,index);
}
}
void Joi(int32_t n, int32_t m, int32_t a[], int32_t b[], long long val, int32_t t){
DSU dsu;
dsu.init(n+5);
for(int x=0;x<m;x++){
if(dsu.unite(a[x],b[x])){
adj2[a[x]].push_back(b[x]);
adj2[b[x]].push_back(a[x]);
}
}
dfs3(0,-1);
for(int x=0;x<60;x++){
if(val&(1LL<<x)){
for(auto it:storage2[x]){
MessageBoard(it,1);
cout << it << endl;
}
}
else{
for(auto it:storage2[x]){
MessageBoard(it,0);
cout << it << endl;
}
}
}
}
struct DSU{
vector<int>e;
void init(int n){
e=vector<int>(n,-1);
}
int get(int x){
return e[x]<0?x:e[x]=get(e[x]);
}
bool unite(int x, int y){
x=get(x); y=get(y);
if(x==y) return 0;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y];
e[y]=x;
return 1;
}
};
vector<int>adj[10005];
int in[10005];
int ptr=-1;
int pp[10005];
void dfs(int index, int par){
in[index]=++ptr;
for(auto it:adj[index]){
if(it==par) continue;
dfs(it,index);
pp[it]=index;
}
}
int ans[60];
int cnt=0;
void f(int index){
if(cnt>200) return;
//cout << index << " index" << endl;
cnt++;
int hold=Move(index);
ans[in[index]%60]=hold;
}
bool visited[10005];
void dfs2(int index, int par){
//if(par!=-1) f(index);
//cout << index << " add\n";
for(auto it:adj[index]){
if(it==pp[index]) continue;
if(it==par) continue;
//cout << index << " " << it << " hm" << endl;
//cout << index << " " << it << " nxt" << endl;
f(it);
dfs2(it,index);
}
//cout << index << " " << pp[index] << endl;
//cout << index << " done\n";
if(pp[index]==-1) return;
else if(par==-1){
f(pp[index]);
dfs2(pp[index],-1);
}
else f(par);
}
long long Ioi(int32_t n, int32_t m, int32_t a[], int32_t b[], int32_t p, int32_t v, int32_t t){
DSU dsu;
dsu.init(n+5);
for(int x=0;x<m;x++){
if(dsu.unite(a[x],b[x])){
adj[a[x]].push_back(b[x]);
adj[b[x]].push_back(a[x]);
cout << a[x] << " " << b[x] << " edge\n";
}
}
memset(pp,-1,sizeof(pp));
dfs(0,-1);
memset(ans,-1,sizeof(ans));
ans[in[p]%60]=v;
dfs2(p,-1);
long long take=0;
for(int x=0;x<60;x++){
if(ans[x]==-1) ans[x]=0;
take+=(1LL<<x)*ans[x];
//cout << take << endl;
//cout << x << " " << ans[x] << endl;
}
//cout << take << " take" << endl;
return take;
}