oj.uz

Submission #710695

# Submission time Handle Problem Language Result Execution time Memory
710695 2023-03-15T15:34:33 Z dum123 Amusement Park (JOI17_amusement_park) C++14
70 / 100
 272 ms 21016 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;



struct node{
	int idx = -1, visited = 0, val=0, before;
	vector<int> adj;
} nodes[200069];

vector<int> BinaryConvert(long long X){
	vector<int> res;
	
	while(X > 0){
		res.push_back(X % 2);
		X/=2;
	}
	
	while(res.size()<60) res.push_back(0);
	return res;
}

int id=0; vector<int> bit;
void dfs(int idBefore, int idNow){
	node now= nodes[idNow];
	if(now.visited == 1) return;
	nodes[idNow].visited = 1;
	nodes[idNow].idx = id++;
	nodes[idNow].val = bit[nodes[idNow].idx % 60];
//	cout<<"Message "<<nodes[idNow].idx<< " : "<<nodes[idNow].val<<endl;
	MessageBoard(idNow, nodes[idNow].val);

	nodes[idNow].before= idBefore;

	for(int i=0;i<nodes[idNow].adj.size();i++){
		dfs(idNow, nodes[idNow].adj[i]);
	}
}

int par[200069];
int findParent(int x){
	if(x==par[x]) return x;
	return findParent(par[x]);
}


void Joi(int N, int M, int A[], int B[], long long X, int T) {
	
	bit = BinaryConvert(X);
	
	for(int i=0;i<N;i++) par[i]=i;
	for(int i=0;i<M;i++){
			
		if(findParent(A[i])!=findParent(B[i])){
			
//		cout<<A[i]<<" - "<<B[i]<<endl;
		nodes[A[i]].adj.push_back(B[i]);
		nodes[B[i]].adj.push_back(A[i]);
		par[findParent(B[i])] = findParent(A[i]);
		}
	}
	
	//DFS dulu ges di node 0
	dfs(-1,0);
	

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

struct node2{
	int idx = -1, visited = 0, val, before=-1, counted = 0;
	vector<int> adj;
} nodes2[200069];


int id2=0, bit2[60], countt2=0; 
void dfs2(int idBefore, int idNow){
	
	if(nodes2[idNow].visited) return;
	nodes2[idNow].visited=1;
	nodes2[idNow].idx = id2++;
	nodes2[idNow].before= idBefore;
	
	for(int i=0;i<nodes2[idNow].adj.size();i++){
		dfs2(idNow, nodes2[idNow].adj[i]);
	}
}

void solveDFS(int idNow, int bitInside){
	

	node2 now = nodes2[idNow];
//	cout<<now.idx<<endl;
//	cout<<"track count: "<<countt2<<"and now.before "<<now.before<<endl;
	if(!nodes2[idNow].counted){
	if(bit2[now.idx % 60] == -1) countt2++;
	bit2[now.idx % 60] = bitInside;
//	cout<<now.idx<<" "<<bit2[idNow]<<endl;
	nodes2[idNow].counted = 1; 
			for(int i=0;i<now.adj.size();i++){
				if (now.adj[i]==now.before) continue;
				if(!nodes2[now.adj[i]].counted) {
					solveDFS(now.adj[i], Move(now.adj[i]));
					if(countt2<60) Move(idNow);
					else return;
				}
				
				
			}

	//kalau uda cek semua anak"nya ya pindah ke ibunya diatas 1
//	if(idNow==5) cout<<"before 5"<<now.before<<endl;
	if(now.before != -1){
		if(!nodes2[now.before].counted && countt2<60){
//		cout<<"use here"; 
		solveDFS(now.before, Move(now.before));
		}
	}

	}

	

}


int par2[200069];
int findParent2(int x){
	if(x==par2[x]) return x;
	return findParent2(par2[x]);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	for(int i=0;i<N;i++) par2[i]=i;
	for(int i=0;i<M;i++){
		if(findParent2(A[i])!=findParent2(B[i])){
		nodes2[A[i]].adj.push_back(B[i]);
		nodes2[B[i]].adj.push_back(A[i]);
		par2[findParent2(B[i])] = findParent2(A[i]);
		}
	}
	
	//DFS dulu ges di node 0
	dfs2(-1,0);
	
	//Solve
	memset(bit2, -1, sizeof(bit2));
	solveDFS(P,V);
	
	
	
	//Convert to decimal
	long long key = 1, res= 0;
	for(int i=0;i<60;i++){
		res += bit2[i] * key;
		key*=2;
	}
	
  return res;
}

Compilation message

Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<nodes[idNow].adj.size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~~~~

Ioi.cpp: In function 'void dfs2(int, int)':
Ioi.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<nodes2[idNow].adj.size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void solveDFS(int, int)':
Ioi.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(int i=0;i<now.adj.size();i++){
      |                ~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17948 KB Output is correct
2 Correct 11 ms 17860 KB Output is correct
3 Correct 11 ms 17936 KB Output is correct
4 Correct 10 ms 17936 KB Output is correct
5 Correct 11 ms 17936 KB Output is correct
6 Correct 10 ms 17936 KB Output is correct
7 Correct 10 ms 17936 KB Output is correct
8 Correct 10 ms 17940 KB Output is correct
9 Correct 10 ms 17936 KB Output is correct
10 Correct 10 ms 17952 KB Output is correct
11 Correct 12 ms 18120 KB Output is correct
12 Correct 10 ms 17936 KB Output is correct
13 Correct 10 ms 17952 KB Output is correct
14 Correct 11 ms 17944 KB Output is correct
15 Correct 9 ms 17952 KB Output is correct
16 Correct 10 ms 17944 KB Output is correct
17 Correct 11 ms 17968 KB Output is correct
18 Correct 10 ms 17952 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 20080 KB Output is correct
2 Correct 153 ms 19840 KB Output is correct
3 Correct 157 ms 19964 KB Output is correct
4 Correct 29 ms 19488 KB Output is correct
5 Correct 24 ms 20516 KB Output is correct
6 Correct 25 ms 20144 KB Output is correct
7 Correct 25 ms 20132 KB Output is correct
8 Correct 22 ms 20392 KB Output is correct
9 Correct 22 ms 20240 KB Output is correct
10 Correct 266 ms 19672 KB Output is correct
11 Correct 258 ms 19740 KB Output is correct
12 Correct 25 ms 19500 KB Output is correct
13 Correct 23 ms 19488 KB Output is correct
14 Correct 23 ms 19496 KB Output is correct
15 Correct 32 ms 19488 KB Output is correct
16 Correct 33 ms 19500 KB Output is correct
17 Correct 27 ms 19492 KB Output is correct
18 Correct 28 ms 19444 KB Output is correct
19 Correct 25 ms 19492 KB Output is correct
20 Correct 24 ms 20488 KB Output is correct
21 Correct 19 ms 20516 KB Output is correct
22 Correct 25 ms 20000 KB Output is correct
23 Correct 24 ms 20272 KB Output is correct
24 Correct 24 ms 20100 KB Output is correct
25 Correct 22 ms 20416 KB Output is correct
26 Correct 22 ms 20312 KB Output is correct
27 Correct 23 ms 20396 KB Output is correct
28 Correct 20 ms 20380 KB Output is correct
29 Correct 22 ms 20104 KB Output is correct
30 Correct 24 ms 20072 KB Output is correct
31 Correct 11 ms 17940 KB Output is correct
32 Correct 10 ms 17940 KB Output is correct
33 Correct 11 ms 17940 KB Output is correct
34 Correct 10 ms 17948 KB Output is correct
35 Correct 11 ms 17940 KB Output is correct
36 Correct 10 ms 17980 KB Output is correct
37 Correct 10 ms 17828 KB Output is correct
38 Correct 11 ms 17948 KB Output is correct
39 Correct 11 ms 17944 KB Output is correct
40 Correct 10 ms 17940 KB Output is correct
41 Correct 10 ms 17948 KB Output is correct
42 Correct 9 ms 17944 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17940 KB Output is correct
2 Correct 9 ms 17936 KB Output is correct
3 Correct 10 ms 17944 KB Output is correct
4 Incorrect 13 ms 18484 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
52.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 20036 KB Output is correct
2 Partially correct 156 ms 20212 KB Partially correct
3 Correct 156 ms 20320 KB Output is correct
4 Correct 24 ms 19512 KB Output is correct
5 Correct 23 ms 21016 KB Output is correct
6 Correct 24 ms 20388 KB Output is correct
7 Correct 22 ms 20264 KB Output is correct
8 Correct 24 ms 20012 KB Output is correct
9 Correct 24 ms 20160 KB Output is correct
10 Correct 272 ms 19612 KB Output is correct
11 Correct 266 ms 19648 KB Output is correct
12 Correct 23 ms 19432 KB Output is correct
13 Correct 20 ms 19484 KB Output is correct
14 Correct 22 ms 19432 KB Output is correct
15 Partially correct 30 ms 19484 KB Partially correct
16 Correct 32 ms 19496 KB Output is correct
17 Partially correct 28 ms 19544 KB Partially correct
18 Partially correct 26 ms 19492 KB Partially correct
19 Correct 26 ms 19496 KB Output is correct
20 Correct 19 ms 20532 KB Output is correct
21 Correct 19 ms 20524 KB Output is correct
22 Correct 23 ms 20176 KB Output is correct
23 Correct 22 ms 20140 KB Output is correct
24 Correct 24 ms 20088 KB Output is correct
25 Correct 23 ms 20384 KB Output is correct
26 Correct 23 ms 20224 KB Output is correct
27 Correct 23 ms 20576 KB Output is correct
28 Correct 22 ms 20080 KB Output is correct
29 Correct 24 ms 19948 KB Output is correct
30 Correct 23 ms 20120 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 20108 KB Output is correct
2 Correct 155 ms 20276 KB Output is correct
3 Correct 152 ms 20132 KB Output is correct
4 Incorrect 27 ms 19520 KB Output isn't correct
5 Halted 0 ms 0 KB -