oj.uz

Submission #702958

# Submission time Handle Problem Language Result Execution time Memory
702958 2023-02-25T11:28:12 Z jamezzz Amusement Park (JOI17_amusement_park) C++17
10 / 100
 598 ms 138212 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 10005
#define pb push_back

namespace joi{
	int num[maxn];
	bool in[maxn],vis[maxn];
	vector<int> v[maxn],AL[maxn];
	void dfs(int u,int p,vector<int> stuff);
	void proc();
}

void joi::dfs(int u,int p,vector<int> stuff){
	vis[u]=true;
	bool have=false;
	for(int i:stuff){
		if(i==u)have=true;
	}
	if(!have){
		int rem=-1;
		for(int i:stuff)in[i]=true;
		for(int i:stuff){
			int deg=0;
			for(int j:AL[i])deg+=in[j];
			if(deg==1&&i!=p){
				rem=i;
				break;
			}
		}
		for(int i:stuff)in[i]=false;
		num[u]=num[rem];
		vector<int> tmp;
		for(int i:stuff){
			if(i!=rem)tmp.pb(i);
		}
		tmp.pb(u);
		swap(tmp,stuff);
	}
	v[u]=stuff;
	for(int v:AL[u]){
		if(v!=p&&!vis[v])dfs(v,u,stuff);
	}
}

void joi::proc(){
	queue<int> q;
	q.push(0);
	v[0].pb(0);
	in[0]=true;
	while(v[0].size()!=60){
		int u=q.front();
		q.pop();
		for(int x:AL[u]){
			if(in[x])continue;
			v[0].pb(x);
			in[x]=true;
			q.push(x);
		}
	}
	for(int i=0;i<60;++i){
		num[v[0][i]]=i;
		in[v[0][i]]=false;
	}
	dfs(0,-1,v[0]);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	for(int i=0;i<N;++i){
		joi::vis[i]=false;
	}
	for(int i=0;i<N-1;++i){
		joi::AL[A[i]].pb(B[i]);
		joi::AL[B[i]].pb(A[i]);
	}
	joi::proc();
	for(int i=0;i<N;++i){
		if(X&(1ll<<joi::num[i]))MessageBoard(i,1);
		else MessageBoard(i,0);
	}
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 10005
#define pb push_back

namespace ioi{
	int num[maxn];
	bool in[maxn],vis[maxn];
	vector<int> v[maxn],AL[maxn];
	void dfs(int u,int p,vector<int> stuff);
	void proc();
}

void ioi::dfs(int u,int p,vector<int> stuff){
	vis[u]=true;
	bool have=false;
	for(int i:stuff){
		if(i==u)have=true;
	}
	if(!have){
		int rem=-1;
		for(int i:stuff)in[i]=true;
		for(int i:stuff){
			int deg=0;
			for(int j:AL[i])deg+=in[j];
			if(deg==1&&i!=p){
				rem=i;
				break;
			}
		}
		for(int i:stuff)in[i]=false;
		num[u]=num[rem];
		vector<int> tmp;
		for(int i:stuff){
			if(i!=rem)tmp.pb(i);
		}
		tmp.pb(u);
		swap(tmp,stuff);
	}
	v[u]=stuff;
	for(int v:AL[u]){
		if(v!=p&&!vis[v])dfs(v,u,stuff);
	}
}

void ioi::proc(){
	queue<int> q;
	q.push(0);
	v[0].pb(0);
	in[0]=true;
	while(v[0].size()!=60){
		int u=q.front();
		q.pop();
		for(int x:AL[u]){
			if(in[x])continue;
			v[0].pb(x);
			in[x]=true;
			q.push(x);
		}
	}
	for(int i=0;i<60;++i){
		num[v[0][i]]=i;
		in[v[0][i]]=false;
	}
	dfs(0,-1,v[0]);
}

int write[maxn];

void dfs2(int u,int p){
	for(int v:ioi::AL[u]){
		if(v==p||!ioi::in[v])continue;
		write[v]=Move(v);
		dfs2(v,u);
		Move(u);
	}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	for(int i=0;i<N;++i){
		ioi::vis[i]=false;
	}
	for(int i=0;i<N-1;++i){
		ioi::AL[A[i]].pb(B[i]);
		ioi::AL[B[i]].pb(A[i]);
	}
	ioi::proc();
	write[P]=V;
	for(int i:ioi::v[P])ioi::in[i]=true;
	dfs2(P,-1);
	long long ans=0;
	for(int i:ioi::v[P]){
		ans^=((long long)write[i]<<ioi::num[i]);
	}
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1544 KB Output is correct
2 Correct 2 ms 1676 KB Output is correct
3 Correct 2 ms 1808 KB Output is correct
4 Correct 2 ms 1676 KB Output is correct
5 Correct 3 ms 1780 KB Output is correct
6 Runtime error 2 ms 1348 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 2772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1800 KB Output is correct
2 Correct 1 ms 1804 KB Output is correct
3 Correct 2 ms 1804 KB Output is correct
4 Correct 6 ms 3896 KB Output is correct
5 Correct 6 ms 3864 KB Output is correct
6 Correct 6 ms 3896 KB Output is correct
7 Correct 5 ms 3896 KB Output is correct
8 Correct 6 ms 3896 KB Output is correct
9 Correct 36 ms 16212 KB Output is correct
10 Correct 37 ms 16068 KB Output is correct
11 Correct 30 ms 16108 KB Output is correct
12 Correct 2 ms 1676 KB Output is correct
13 Correct 1 ms 1796 KB Output is correct
14 Correct 1 ms 1548 KB Output is correct
15 Correct 2 ms 1564 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 598 ms 136616 KB Wrong Answer [8]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 597 ms 138212 KB Wrong Answer [8]
2 Halted 0 ms 0 KB -