oj.uz

Submission #558769

# Submission time Handle Problem Language Result Execution time Memory
558769 2022-05-08T09:57:38 Z Trunkty Amusement Park (JOI17_amusement_park) C++14
0 / 100
 28 ms 6132 KB 
#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){
		cout << pa << "\n";
		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;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1548 KB Output is correct
2 Correct 4 ms 1544 KB Output is correct
3 Correct 3 ms 1804 KB Output is correct
4 Incorrect 2 ms 1604 KB Do not print anything on standard output.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 6132 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1548 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 6080 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 6060 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -