| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1155236 | KhoaDuy | Amusement Park (JOI17_amusement_park) | C++20 | 0 ms | 0 KiB |
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MAXN=10000;
int dsu[MAXN];
int in[MAXN];
int tim=0;
vector<vector<int>> graph;
int pa[MAXN];
int Findset(int i){
if(dsu[i]<0){
return i;
}
int root=Findset(dsu[i]);
dsu[i]=root;
return root;
}
void unite(int u,int v){
u=Findset(u),v=Findset(v);
if(u==v){
return;
}
if(dsu[u]<dsu[v]){
swap(u,v);
}
dsu[v]+=dsu[u];
dsu[u]=v;
}
void setup(int u,int p){
pa[u]=p;
in[u]=tim;
tim++;
for(int v:graph[u]){
if(v!=p){
setup(v,u);
}
}
}
void buildtree(int a[],int b[],int n,int m){
graph.clear();
graph.resize(n);
tim=0;
for(int i=0;i<n;i++){
dsu[i]=-1,in[i]=0,pa[i]=0;
}
for(int i=0;i<m;i++){
if(Findset(a[i])!=Findset(b[i])){
unite(a[i],b[i]);
graph[a[i]].push_back(b[i]);
graph[b[i]].push_back(a[i]);
}
}
setup(0,-1);
}
void Joi(int n,int m,int a[],int b[],long long x,int t){
buildtree(a,b,n,m);
for(int i=0;i<n;i++){
int bit=(x&(1LL<<(in[i]%60)));
bit>>=(in[i]%60);
MessageBoard(i,bit);
}
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MAXN=10000;
int dsu[MAXN];
int in[MAXN];
int tim=0;
vector<vector<int>> graph;
int pa[MAXN];
int Findset(int i){
if(dsu[i]<0){
return i;
}
int root=Findset(dsu[i]);
dsu[i]=root;
return root;
}
void unite(int u,int v){
u=Findset(u),v=Findset(v);
if(u==v){
return;
}
if(dsu[u]<dsu[v]){
swap(u,v);
}
dsu[v]+=dsu[u];
dsu[u]=v;
}
void setup(int u,int p){
pa[u]=p;
in[u]=tim;
tim++;
for(int v:graph[u]){
if(v!=p){
setup(v,u);
}
}
}
void buildtree(int a[],int b[],int n,int m){
graph.clear();
graph.resize(n);
tim=0;
for(int i=0;i<n;i++){
dsu[i]=-1,in[i]=0,pa[i]=0;
}
for(int i=0;i<m;i++){
if(Findset(a[i])!=Findset(b[i])){
unite(a[i],b[i]);
graph[a[i]].push_back(b[i]);
graph[b[i]].push_back(a[i]);
}
}
setup(0,-1);
}
long long x=-1;
int val[60];
int write[MAXN];
void update(int k,int bit){
val[k]=bit;
bool flag=true;
for(int i=0;i<60;i++){
if(val[i]==-1){
flag=false;
break;
}
}
if(flag){
x=0;
for(int i=0;i<60;i++){
if(val[i]){
x^=(1LL<<i);
}
}
}
}
void DFS(int u,int p,char dir){
update(in[u]%60,write[u]);
if(x!=-1){
return;
}
if(dir=='R'){
for(int i=(int)graph[u].size()-1;i>=0;i--){
int v=graph[u][i];
if(v!=p){
write[v]=Move(v);
DFS(v,u,dir);
if(x!=-1){
return;
}
write[u]=Move(u);
}
}
}
else{
for(int v:graph[u]){
if(v!=p){
write[v]=Move(v);
DFS(v,u,dir);
if(x!=-1){
return;
}
write[u]=Move(u);
}
}
}
}
long long Ioi(int n,int m,int a[],int b[],int u,int V,int t){
memset(val,-1,sizeof(val));
buildtree(a,b,n,m);
write[u]=V;
int last=-1;
while(x==-1&&u!=-1){
update(in[u]%60,write[u]);
if(x!=-1){
return x;
}
int pos=-1;
for(int i=0;i<graph[u].size();i++){
int v=graph[u][i];
if(v!=pa[u]&&v==last){
pos=i;
break;
}
}
for(int i=pos-1;i>=0;i--){
int v=graph[u][i];
if(v!=pa[u]){
write[v]=Move(v);
DFS(v,u,'R');
write[u]=Move(u);
if(x!=-1){
return x;
}
}
}
for(int i=pos+1;i<graph[u].size();i++){
int v=graph[u][i];
if(v!=pa[u]){
write[v]=Move(v);
DFS(v,u,'L');
write[u]=Move(u);
if(x!=-1){
return x;
}
}
}
u=pa[u];
if(u!=-1){
write[u]=Move(u);
}
}
return x;
}