oj.uz

Submission #514817

# Submission time Handle Problem Language Result Execution time Memory
514817 2022-01-18T14:03:45 Z amunduzbaev Amusement Park (JOI17_amusement_park) C++14
10 / 100
 57 ms 5628 KB 
#include "bits/stdc++.h"
using namespace std;
#include "Joi.h"

const int N = 1e4 + 5;
vector<int> G[N], tt;
int used[N], in[N], cnt = 1;
bool gg[60][60];

void dfs(int u){
	used[u] = 1;
	for(auto x : G[u]){
		if(used[x]) continue;
		if(cnt < 60){
			tt.push_back(x);
			in[x] = cnt++;
			gg[in[u]][in[x]] = gg[in[x]][in[u]] = 1;
		} else {
			for(int i=0;i<60;i++){
				if(i == in[u]) continue;
				int cc = 0;
				for(int j=0;j<60;j++) cc += gg[i][j];
				if(cc > 1) continue;
				for(int j=0;j<60;j++) gg[i][j] = gg[j][i] = 0;
				tt[i] = x;
				gg[in[u]][i] = gg[i][in[u]] = 1;
				in[x] = i;
				break;
			}
		}
		dfs(x);
		
		if(tt[in[u]] != u){
			for(int j=0;j<60;j++) gg[in[u]][j] = gg[j][in[u]] = 0;
			tt[in[u]] = u;
			gg[in[u]][in[x]] = gg[in[x]][in[u]] = 1;
		}
	}
}

void Joi(int n, int m, int a[], int b[], long long x, int t){
	for(int i=0;i<m;i++){
		G[a[i]].push_back(b[i]);
		G[b[i]].push_back(a[i]);
	} for(int i=0;i<n;i++){
		sort(G[i].begin(), G[i].end());
	}
	
	tt.push_back(0);
	memset(in, -1, sizeof in);
	in[0] = 0; dfs(0);
	
	//~ for(int i=0;i<n;i++) cout<<in[i]<<" ";
	//~ cout<<"\n";
	
	for(int i=0;i<n;i++){
		assert(~in[i]);
		MessageBoard(i, x >> in[i] & 1);
	}
}

#include "bits/stdc++.h"
using namespace std;
#include "Ioi.h"
const int N = 1e4 + 5;
vector<int> G[N], tt, ee[N];
int used[N], in[N], cnt = 1;
bool gg[60][60], uu[60];

void dfs(int u){
	used[u] = 1;
	for(auto x : G[u]){
		if(used[x]) continue;
		ee[u].push_back(x);
		ee[x].push_back(u);
		if(cnt < 60){
			tt.push_back(x);
			in[x] = cnt++;
			gg[in[u]][in[x]] = gg[in[x]][in[u]] = 1;
		} else {
			for(int i=0;i<60;i++){
				if(i == in[u]) continue;
				int cc = 0;
				for(int j=0;j<60;j++) cc += gg[i][j];
				if(cc > 1) continue;
				for(int j=0;j<60;j++) gg[i][j] = gg[j][i] = 0;
				tt[i] = x;
				gg[in[u]][i] = gg[i][in[u]] = 1;
				in[x] = i;
				break;
			}
		}
		dfs(x);
		
		if(tt[in[u]] != u){
			for(int j=0;j<60;j++) gg[in[u]][j] = gg[j][in[u]] = 0;
			tt[in[u]] = u;
			gg[in[u]][in[x]] = gg[in[x]][in[u]] = 1;
		}
	}
}

long long Ioi(int n, int m, int a[], int b[], int p, int v, int t){
	for(int i=0;i<m;i++){
		G[a[i]].push_back(b[i]);
		G[b[i]].push_back(a[i]);
	} for(int i=0;i<n;i++){
		sort(G[i].begin(), G[i].end());
	}
	
	tt.push_back(0);
	memset(in, -1, sizeof in);
	in[0] = 0; dfs(0);
	
	//~ for(int i=0;i<n;i++) cout<<in[i]<<" ";
	//~ cout<<"\n";
	
	memset(used, 0, sizeof used);
	long long x = 0;
	function<void(int)> go = [&](int u){
		used[u] = uu[in[u]] = 1;
		if(v) x |= (1ll << in[u]);
		for(auto x : ee[u]){
			if(used[x] || uu[in[x]]) continue;
			v = Move(x), go(x),
			v = Move(u);
		}
	};
	go(p);
	
	return x;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1516 KB Output is correct
2 Correct 1 ms 1524 KB Output is correct
3 Correct 2 ms 1528 KB Output is correct
4 Correct 1 ms 1516 KB Output is correct
5 Correct 2 ms 1444 KB Output is correct
6 Correct 2 ms 1444 KB Output is correct
7 Incorrect 2 ms 1524 KB Wrong Answer [7]
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 5288 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1516 KB Output is correct
2 Correct 1 ms 1472 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 6 ms 1980 KB Output is correct
5 Correct 8 ms 2068 KB Output is correct
6 Correct 7 ms 2072 KB Output is correct
7 Correct 7 ms 2080 KB Output is correct
8 Correct 7 ms 2080 KB Output is correct
9 Correct 37 ms 5124 KB Output is correct
10 Correct 35 ms 5120 KB Output is correct
11 Correct 34 ms 5200 KB Output is correct
12 Correct 1 ms 1516 KB Output is correct
13 Correct 2 ms 1524 KB Output is correct
14 Correct 2 ms 1520 KB Output is correct
15 Correct 2 ms 1520 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5336 KB Output is correct
2 Correct 48 ms 5404 KB Output is correct
3 Incorrect 53 ms 5628 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5256 KB Output is correct
2 Incorrect 45 ms 5288 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -