Submission #1003673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003673		jamjanek	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	18 ms	3884 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
int distJ[10010];
bool odwJ[10010];
int fatherJ[10010], ojciecJ[10010];
vector<int>grafJ[10010];
int findJ(int x){
	if(fatherJ[x]==x)return x;
	return fatherJ[x] = findJ(fatherJ[x]);
}
int preorder[10010], preorder2[10010];
int preitJ;
void dfs(int x, int o){
	preorder[x] = preitJ++;
	for(auto j: grafJ[x])
		if(j!=o)
			dfs(j, x);
}
void dfs2(int x, int o){
	preorder2[x] = preitJ++;
	for(auto j: grafJ[x])
		if(j!=o && preorder[j]<60)
			dfs2(j, x);
}
void Joi(int n, int m, int a[], int b[], long long x, int t) {
	//printf("Joi\n");
	//f&u zeby zrobic drzewo
	int i;
	for(i=0;i<n;i++)fatherJ[i] = i;
	for(i=0;i<m;i++){
		if(findJ(a[i])!=findJ(b[i])){
			grafJ[a[i]].push_back(b[i]), grafJ[b[i]].push_back(a[i]);
			fatherJ[fatherJ[a[i]]] = fatherJ[b[i]];
		}
	}

	queue<int>kolejka;
	kolejka.push(0);
	distJ[0] = 1;
	int w;
	while(kolejka.size()){
		w = kolejka.front();
		kolejka.pop();
		for(auto j: grafJ[w])
			if(distJ[j]==0){
				distJ[j] = distJ[w]+1;
				kolejka.push(j);
			}
	}
	for(i=0;i<n;i++){
		distJ[i] = 0;
	}
	kolejka.push(w);
	distJ[w] = 1;
	int k = w;
	ojciecJ[w] = -1;
	while(kolejka.size()){
		w = kolejka.front();
		kolejka.pop();
		for(auto j: grafJ[w])
			if(distJ[j]==0){
				ojciecJ[j] = w;
				distJ[j] = distJ[w]+1;
				kolejka.push(j);
			}
	}
	if(distJ[w]>=60){
		//printf("Case 1\n");
		for(i=0;i<n;i++){
			int pom = distJ[i]-1;
			pom = pom%60;
			MessageBoard(i, (x>>pom)&1);
		}
		return;
	}
	else{
		//printf("Case 2\n");
		int pom1 = ojciecJ[w], pom2 = w;
		while(pom1!=-1){
			for(int i=0;i<(int)grafJ[pom1].size();i++)
				if(grafJ[pom1][i]==pom2){
					swap(grafJ[pom1][i], grafJ[pom1][0]);
					break;
				}
			pom2 = pom1;
			pom1 = ojciecJ[pom1];
		}
		dfs(k, k);
		
		pom1 = ojciecJ[w], pom2 = w;
		while(pom1!=-1){
			for(auto &ij: grafJ[pom1])
				if(ij==pom2){
					swap(ij, grafJ[pom1].back());
					break;
				}
			pom2 = pom1;
			pom1 = ojciecJ[pom1];
		}
		preitJ=0;
		dfs2(k, k);
		
		for(i=0;i<n;i++){
			if(preorder2[i]<60)
				MessageBoard(i, (x>>preorder2[i])&1);
			else
				MessageBoard(i, 0);
		}
		return;
	}
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
int dist[10010];
bool odw[10010];
int father[10010];
int ojciec[10010];
vector<int>graf[10010];
int find(int x){
	if(father[x]==x)return x;
	return father[x] = find(father[x]);
}
long long wynik = 0;
int preit=0;
int preorderI[10010];
void dfs1(int x, int o){
	for(auto j: graf[x])
		if(o!=j && preorderI[j]<60){
			if(preit<60)
				wynik+=(1ll<<preit++)*Move(j);
			dfs1(j, x);
		}
	if(preit<60)
		int skip = Move(o);
}

void dfs3(int x, int o){
	preorderI[x] = preit++;
	for(auto j: graf[x])
		if(j!=o)
			dfs3(j, x);
}

long long Ioi(int n, int m, int a[], int b[], int p, int v, int t) {
	//printf("Ioi:\n");
	//f&u zeby zrobic drzewo
	int i;
	for(i=0;i<n;i++)father[i] = i;
	for(i=0;i<m;i++){
		if(find(a[i])!=find(b[i])){
			graf[a[i]].push_back(b[i]), graf[b[i]].push_back(a[i]);
			father[father[a[i]]] = father[b[i]];
		}
	}

	queue<int>kolejka;
	kolejka.push(0);
	dist[0] = 1;
	int w;
	while(kolejka.size()){
		w = kolejka.front();
		kolejka.pop();
		for(auto j: graf[w])
			if(dist[j]==0){
				dist[j] = dist[w]+1;
				kolejka.push(j);
			}
	}
	for(i=0;i<n;i++){
		dist[i] = 0;
	}
	kolejka.push(w);
	dist[w] = 1;
	ojciec[w] = -1;
	int k = w;
	while(kolejka.size()){
		w = kolejka.front();
		kolejka.pop();
		for(auto j: graf[w])
			if(dist[j]==0){
				ojciec[j] = w;
				dist[j] = dist[w]+1;
				kolejka.push(j);
			}
	}
	if(dist[w]>=60){
		//printf("Case 1\n");
		//return 0;
		while((dist[p]-1)%60!=0){
			p = ojciec[p];
			v = Move(p);
		}
		long long res = 0;
		long long pom = 0;
		if(ojciec[p]==-1){
			res = v;
			vector<int>vec;
			while(dist[w]>60)w = ojciec[w];
			while(w!=p){
				vec.push_back(w);
				w = ojciec[w];
			}
			reverse(vec.begin(), vec.end());
			for(auto j: vec){
				pom++;
				res = res + (1ll<<pom)*Move(j);
			}
		}
		else{
			for(i=59;i>=0;i--){
				res = res + (1ll<<i)*Move(ojciec[p]);
				p = ojciec[p];
			}
		}
		//printf("res: %lld\n", res);
		return res;
	}
	else{
		//return 0;
		//printf("Case 2\n");
		while(ojciec[p]!=-1){
			v = Move(ojciec[p]);
			p = ojciec[p];
		}
		
		
		int pom1 = ojciec[w], pom2 = w;
		while(pom1!=-1){
			for(int i=0;i<(int)graf[pom1].size();i++)
				if(graf[pom1][i]==pom2){
					swap(graf[pom1][i], graf[pom1][0]);
					break;
				}
			pom2 = pom1;
			pom1 = ojciec[pom1];
		}
		dfs3(k, k);
		
		pom1 = ojciec[w], pom2 = w;
		while(pom1!=-1){
			for(auto &ij: graf[pom1])
				if(ij==pom2){
					swap(ij, graf[pom1].back());
					break;
				}
			pom2 = pom1;
			pom1 = ojciec[pom1];
		}
		
		
		preit = 1;
		wynik=v;
		dfs1(p, p);
		return wynik;
	}
}

Compilation message (stderr)

Ioi.cpp: In function 'void dfs1(int, int)':
Ioi.cpp:24:7: warning: unused variable 'skip' [-Wunused-variable]
   24 |   int skip = Move(o);
      |       ^~~~

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