oj.uz

Submission #1003644

# Submission time Handle Problem Language Result Execution time Memory
1003644 2024-06-20T14:24:26 Z jamjanek Amusement Park (JOI17_amusement_park) C++14
81 / 100
 15 ms 3920 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
int distJ[10010];
bool odwJ[10010];
int fatherJ[10010];
vector<int>grafJ[10010];
int findJ(int x){
	if(fatherJ[x]==x)return x;
	return fatherJ[x] = findJ(fatherJ[x]);
}
int preorder[10010];
int preitJ;
void dfs(int x, int o){
	preorder[x] = preitJ++;
	for(auto j: grafJ[x])
		if(j!=o)
			dfs(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;
	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);
			}
	}
	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");
		dfs(k, k);
		for(i=0;i<n;i++){
			if(preorder[i]<60)
				MessageBoard(i, (x>>preorder[i])&1);
			else
				MessageBoard(i, 0);
		}
		return;
	}
}

#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=1;
void dfs1(int x, int o){
	for(auto j: graf[x])
		if(o!=j){
			if(preit<60)
				wynik+=(1ll<<preit++)*Move(j);
			dfs1(j, x);
		}
	if(preit<60)
		int skip = Move(o);
}
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;
	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];
		}
		wynik=v;
		dfs1(p, p);
		return wynik;
	}
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1568 KB Output is correct
2 Correct 1 ms 1308 KB Output is correct
3 Correct 1 ms 1316 KB Output is correct
4 Correct 0 ms 1300 KB Output is correct
5 Correct 0 ms 1312 KB Output is correct
6 Correct 1 ms 1312 KB Output is correct
7 Correct 1 ms 1812 KB Output is correct
8 Correct 1 ms 1316 KB Output is correct
9 Correct 0 ms 1316 KB Output is correct
10 Correct 0 ms 1300 KB Output is correct
11 Correct 3 ms 1384 KB Output is correct
12 Correct 0 ms 1300 KB Output is correct
13 Correct 1 ms 1316 KB Output is correct
14 Correct 2 ms 1308 KB Output is correct
15 Correct 0 ms 1316 KB Output is correct
16 Correct 0 ms 1312 KB Output is correct
17 Correct 1 ms 1316 KB Output is correct
18 Correct 1 ms 1308 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3764 KB Output is correct
2 Correct 15 ms 3920 KB Output is correct
3 Correct 14 ms 3868 KB Output is correct
4 Correct 9 ms 3228 KB Output is correct
5 Correct 9 ms 2880 KB Output is correct
6 Correct 9 ms 2868 KB Output is correct
7 Correct 9 ms 2876 KB Output is correct
8 Correct 8 ms 2868 KB Output is correct
9 Correct 10 ms 2864 KB Output is correct
10 Correct 10 ms 3384 KB Output is correct
11 Correct 7 ms 3396 KB Output is correct
12 Correct 8 ms 2916 KB Output is correct
13 Correct 7 ms 2752 KB Output is correct
14 Correct 9 ms 2868 KB Output is correct
15 Correct 9 ms 2880 KB Output is correct
16 Correct 9 ms 3080 KB Output is correct
17 Correct 9 ms 3132 KB Output is correct
18 Correct 9 ms 2884 KB Output is correct
19 Correct 10 ms 2876 KB Output is correct
20 Correct 7 ms 2880 KB Output is correct
21 Correct 7 ms 2872 KB Output is correct
22 Correct 9 ms 2872 KB Output is correct
23 Correct 8 ms 2880 KB Output is correct
24 Correct 8 ms 2872 KB Output is correct
25 Correct 8 ms 2880 KB Output is correct
26 Correct 8 ms 2880 KB Output is correct
27 Correct 8 ms 2872 KB Output is correct
28 Correct 7 ms 2880 KB Output is correct
29 Correct 7 ms 2856 KB Output is correct
30 Correct 8 ms 2872 KB Output is correct
31 Correct 1 ms 1308 KB Output is correct
32 Correct 0 ms 1312 KB Output is correct
33 Correct 0 ms 1304 KB Output is correct
34 Correct 1 ms 1296 KB Output is correct
35 Correct 0 ms 1312 KB Output is correct
36 Correct 0 ms 1312 KB Output is correct
37 Correct 1 ms 1300 KB Output is correct
38 Correct 0 ms 1308 KB Output is correct
39 Correct 0 ms 1300 KB Output is correct
40 Correct 0 ms 1308 KB Output is correct
41 Correct 0 ms 1312 KB Output is correct
42 Correct 0 ms 1312 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1312 KB Output is correct
2 Correct 0 ms 1312 KB Output is correct
3 Correct 0 ms 1312 KB Output is correct
4 Correct 1 ms 1352 KB Output is correct
5 Correct 1 ms 1340 KB Output is correct
6 Correct 3 ms 1352 KB Output is correct
7 Correct 2 ms 1340 KB Output is correct
8 Correct 2 ms 1336 KB Output is correct
9 Correct 5 ms 2752 KB Output is correct
10 Correct 5 ms 2776 KB Output is correct
11 Correct 7 ms 2784 KB Output is correct
12 Correct 0 ms 1308 KB Output is correct
13 Correct 0 ms 1304 KB Output is correct
14 Correct 1 ms 1300 KB Output is correct
15 Correct 0 ms 1308 KB Output is correct

Subtask #4
53.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3420 KB Output is correct
2 Correct 13 ms 3424 KB Output is correct
3 Correct 14 ms 3428 KB Output is correct
4 Partially correct 8 ms 2784 KB Partially correct
5 Correct 9 ms 2880 KB Output is correct
6 Correct 10 ms 2872 KB Output is correct
7 Correct 9 ms 2880 KB Output is correct
8 Correct 9 ms 2868 KB Output is correct
9 Correct 9 ms 2876 KB Output is correct
10 Correct 10 ms 3140 KB Output is correct
11 Correct 9 ms 3388 KB Output is correct
12 Correct 9 ms 2856 KB Output is correct
13 Partially correct 7 ms 2856 KB Partially correct
14 Partially correct 9 ms 2876 KB Partially correct
15 Partially correct 9 ms 2880 KB Partially correct
16 Partially correct 10 ms 2884 KB Partially correct
17 Correct 8 ms 2880 KB Output is correct
18 Partially correct 9 ms 3132 KB Partially correct
19 Partially correct 9 ms 3124 KB Partially correct
20 Correct 7 ms 2864 KB Output is correct
21 Correct 6 ms 2872 KB Output is correct
22 Correct 9 ms 2872 KB Output is correct
23 Correct 9 ms 2876 KB Output is correct
24 Correct 8 ms 2872 KB Output is correct
25 Correct 10 ms 2876 KB Output is correct
26 Correct 9 ms 2880 KB Output is correct
27 Correct 9 ms 2880 KB Output is correct
28 Correct 9 ms 2880 KB Output is correct
29 Correct 7 ms 2852 KB Output is correct
30 Correct 9 ms 2856 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3424 KB Output is correct
2 Correct 14 ms 3424 KB Output is correct
3 Correct 12 ms 3424 KB Output is correct
4 Incorrect 8 ms 2784 KB Output isn't correct
5 Halted 0 ms 0 KB -