Submission #294165

#	Time	Username	Problem	Language	Result	Execution time	Memory
294165		patrikpavic2	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	37 ms	10756 KiB

Joi

#include "Joi.h"
#include <vector>
#include <algorithm>
#include <cstdio>


#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 1e5 + 500;

int dep[N], ppar[N], tr[N], mks[N], par[N];
int tko[N], bit[N], cur = 0;
vector < int > v[N];


int pr(int x){
	if(x == ppar[x]) return x;
	return ppar[x] = pr(ppar[x]);
}

bool cmp(int x, int y){
	return mks[x] > mks[y];
}

int dfs(int x, int lst){
	mks[x] = dep[x]; par[x] = lst;
	vector < int > vv;
	for(int y : v[x]){
		if(y == lst) continue;
		vv.PB(y);
		dep[y] = dep[x] + 1;
		dfs(y, x);
		mks[x] = max(mks[x], mks[y]);
	}
	sort(vv.begin(), vv.end(), cmp);
	v[x] = vv;
	return mks[x];
}

void dfs2(int x){
	if(cur == 60) return;
	tko[x] = cur++; bit[x] = 1;
	//printf("tko[ %d ] = %d bit[ %d ] = %d\n", x, tko[x], x, bit[x]);
	for(int y : v[x])
		dfs2(y);
}

void Joi(int n, int m, int A[], int B[], long long X, int T) {
	for(int i = 0;i < n;i++)
		ppar[i] = i;
	for(int i = 0;i < m;i++){
		if(pr(A[i]) == pr(B[i]))
			continue;
		ppar[pr(A[i])] = pr(B[i]);
		v[A[i]].PB(B[i]);
		v[B[i]].PB(A[i]);
		tr[i] = 1;
	}
	dfs(0, 0);
	if(mks[0] >= 59){
		//printf("Slucaj 1\n");
		for(int i = 0;i < n;i++)
			MessageBoard(i, !!(X & (1LL << (dep[i] % 60))));
		return;
	}
	//printf("Slucaj 2\n");
	dfs2(0);
	for(int i = 0;i < n;i++)
		MessageBoard(i, !!(X & (1LL << tko[i])));
	
}

Ioi

#include "Ioi.h"
#include <vector>
#include <algorithm>
#include <cstdio>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 1e5 + 500;

int dep2[N], ppar22[N], tr2[N], mks2[N], par2[N];
int tko2[N], bit2[N], cur2 = 0;
ll ans = 0;
vector < int > v2[N];

int pr2(int x){
	if(x == ppar22[x]) return x;
	return ppar22[x] = pr2(ppar22[x]);
}

bool cmp2(int x, int y){
	return mks2[x] > mks2[y];
}

int dfs2(int x, int lst){
	mks2[x] = dep2[x]; par2[x] = lst;
	vector < int > v2v2;
	for(int y : v2[x]){
		if(y == lst) continue;
		v2v2.PB(y);
		dep2[y] = dep2[x] + 1;
		dfs2(y, x);
		mks2[x] = max(mks2[x], mks2[y]);
	}
	sort(v2v2.begin(), v2v2.end(), cmp2);
	v2[x] = v2v2;
	return mks2[x];
}

void dfs22(int x){
	if(cur2 == 60) return;
	tko2[x] = cur2++; bit2[x] = 1;
	for(int y : v2[x])
		dfs22(y);
}

int odg2 = -1;

void odg2ov2or(int x, bool nazad){
	ans += (1LL << tko2[x]) * odg2;
	reverse(v2[x].begin(), v2[x].end()); 
	for(int y : v2[x]){
		if(bit2[y]){
			odg2 = Move(y);
			odg2ov2or(y, nazad || (y != v2[x].back()));
			if(y != v2[x].back() || nazad){
				odg2 = Move(x);
			}
		}
	}
	reverse(v2[x].begin(), v2[x].end()); 
}

long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
	for(int i = 0;i < n;i++)
		ppar22[i] = i;
	for(int i = 0;i < m;i++){
		if(pr2(A[i]) == pr2(B[i]))
			continue;
		ppar22[pr2(A[i])] = pr2(B[i]);
		v2[A[i]].PB(B[i]);
		v2[B[i]].PB(A[i]);
		tr2[i] = 1;
	}
	dfs2(0, 0);
	if(mks2[0] >= 59){
		int lst = V;
		//printf("P = %d mks2[ %d ] = %d\n", P, P, mks2[P]);
		while(mks2[P] - dep2[P] < 59){
			lst = Move(par2[P]);
			P = par2[P];
		}
		for(int i = 0;i < 60;i++){
			ans += (1LL << (dep2[P] % 60)) * lst;
			if(i < 59){
				lst = Move(v2[P][0]);
				P = v2[P][0];
			}
		}
		return ans;
	}
	dfs22(0);
	odg2 = V;
	while(P != 0){
		odg2 = Move(par2[P]);
		P = par2[P];
	}
	odg2ov2or(0, 0);
	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17