| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1221755 | MarwenElarbi | Amusement Park (JOI17_amusement_park) | C++20 | 0 ms | 0 KiB |
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
//common
#define pb push_back
#define se second
#define fi first
const int nax=10005;
namespace{
vector<int> parent(nax);
vector<int> tree[nax];
int dp[nax];
int special[nax];
int dep[nax];
vector<int> par(nax);
int find(int x){
if(x==parent[x]) return x;
return parent[x]=find(parent[x]);
}
bool sameset(int x,int y){
return find(x)==find(y);
}
void joinset(int x,int y){
x=find(x);
y=find(y);
parent[x]=y;
}
void dfs(int x,int p){
dp[x]=1;
par[x]=p;
for(auto u:tree[x]){
if(u==p) continue;
dep[u]=dep[x]+1;
dfs(u,x);
if(special[u]) continue;
dp[x]+=dp[u];
}
if(dp[x]>=60){
special[x]=1;
}
}
//1
}
vector<int> cur;
void traversal(int x){
if(cur.size()>=60) return;
cur.pb(x);
for(auto u:tree[x]){
if(u==par[x]) continue;
if(special[u]) continue;
traversal(u);
}
}
vector<int> paint(nax,0);
void Joi(int N, int M, int A[], int B[], long long X, int T){
for (int i = 0; i < N; i++) parent[i]=i;
for (int i = 0; i < M; ++i)
{
if(sameset(A[i],B[i])) continue;
joinset(A[i],B[i]);
tree[A[i]].pb(B[i]);
tree[B[i]].pb(A[i]);
}
dfs(0,-1);
if(!special[0]){
pair<int,int> mn={nax,nax};
for (int i = 0; i < N; ++i)
{
if(special[i]) mn=min(mn,make_pair(dep[i],i));
}
special[0]=1;
special[mn.se]=0;
}
for (int i = 0; i < N; ++i)
{
if(special[i]) {
cur.clear();
traversal(i);
for (int j = 0; j < 60; ++j)
{
if((1ll<<j)&X) paint[cur[j]]=1;
}
}
}
for (int i = 0; i < N; ++i)
{
if(paint[i]){
MessageBoard(i,1);
}else MessageBoard(i,0);
}
return;
}
#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
#define pb push_back
#define se second
#define fi first
const int nax=100005;
namespace{
vector<int> parent(nax);
vector<int> tree[nax];
int dp[nax];
int special[nax];
int dep[nax];
vector<int> par(nax);
int find(int x){
if(x==parent[x]) return x;
return parent[x]=find(parent[x]);
}
bool sameset(int x,int y){
return find(x)==find(y);
}
void joinset(int x,int y){
x=find(x);
y=find(y);
parent[x]=y;
}
void dfs(int x,int p){
dp[x]=1;
par[x]=p;
for(auto u:tree[x]){
if(u==p) continue;
dep[u]=dep[x]+1;
dfs(u,x);
if(special[u]) continue;
dp[x]+=dp[u];
}
if(dp[x]>=60){
special[x]=1;
}
}
vector<int> cte;
void trav(int x){
if(cte.size()>=60) return;
for(auto u:tree[x]){
if(cte.size()>=60) return;
if(u==par[x]) continue;
if(special[u]) continue;
cte.pb(Move(u));
trav(u);
if(cte.size()>=60) return;
Move(x);
}
}
}
vector<int> cte;
void trav(int x){
if(cte.size()>=60) return;
for(auto u:tree[x]){
if(cte.size()>=60) return;
if(u==par[x]) continue;
if(special[u]) continue;
cte.pb(Move(u));
trav(u);
if(cte.size()>=60) return;
Move(x);
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
for (int i = 0; i < N;++i)
{
parent[i]=i;
tree[i].clear();
dp[i]=0;
special[i]=0;
}
for (int i = 0; i < M; ++i)
{
if(sameset(A[i],B[i])) continue;
joinset(A[i],B[i]);
tree[A[i]].pb(B[i]);
tree[B[i]].pb(A[i]);
}
dfs(0,-1);
if(!special[0]){
pair<int,int> mn={nax,nax};
for (int i = 0; i < N; ++i)
{
if(special[i]) mn=min(mn,make_pair(dep[i],i));
}
special[0]=1;
special[mn.se]=0;
}
if(!special[P]){
while(!special[par[P]]) {
P=par[P];
Move(P);
}
cte.clear();
cte.pb(Move(par[P]));
P=par[P];
}else cte.push_back(V);
trav(P);
long long ans=0;
for (int i = 0; i < 60; ++i)
{
ans+=1ll*(cte[i]<<i);
}
cte.clear();
return ans;
}