oj.uz

Submission #1003641

# Submission time Handle Problem Language Result Execution time Memory
1003641 2024-06-20T14:20:32 Z jamjanek Amusement Park (JOI17_amusement_park) C++14
10 / 100
 18 ms 3496 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{
		return;
		//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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1308 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3428 KB Output is correct
2 Correct 14 ms 3424 KB Output is correct
3 Correct 18 ms 3264 KB Output is correct
4 Incorrect 4 ms 1800 KB Wrong Answer [4]
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1292 KB Output is correct
2 Correct 0 ms 1296 KB Output is correct
3 Correct 1 ms 1308 KB Output is correct
4 Correct 2 ms 1324 KB Output is correct
5 Correct 2 ms 1336 KB Output is correct
6 Correct 2 ms 1340 KB Output is correct
7 Correct 2 ms 1340 KB Output is correct
8 Correct 2 ms 1332 KB Output is correct
9 Correct 7 ms 2788 KB Output is correct
10 Correct 6 ms 2980 KB Output is correct
11 Correct 6 ms 2772 KB Output is correct
12 Correct 0 ms 1308 KB Output is correct
13 Correct 0 ms 1308 KB Output is correct
14 Correct 0 ms 1296 KB Output is correct
15 Correct 0 ms 1308 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3416 KB Output is correct
2 Correct 15 ms 3496 KB Output is correct
3 Correct 14 ms 3424 KB Output is correct
4 Incorrect 3 ms 1808 KB Wrong Answer [4]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3424 KB Output is correct
2 Correct 16 ms 3424 KB Output is correct
3 Correct 14 ms 3488 KB Output is correct
4 Incorrect 3 ms 1816 KB Wrong Answer [4]
5 Halted 0 ms 0 KB -