oj.uz

Submission #711762

# Submission time Handle Problem Language Result Execution time Memory
711762 2023-03-17T12:38:16 Z dum123 Amusement Park (JOI17_amusement_park) C++14
100 / 100
 382 ms 207864 KB 
#include "Joi.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

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

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

bool connected[10069][10069];

void CopyTree (int target, int neighbor){
	int adjCount[10069], cut;
	memset(adjCount, 0, sizeof(adjCount));
	
	vector<int> pohon = nodes[neighbor].tree;
	for(int i = 0; i < pohon.size() ; i++){
		int u = pohon[i];
		for(int j = i+1; j< pohon.size(); j++){
		 	int v = pohon[j];
			if(connected[u][v]){
				adjCount[u]++; adjCount[v]++;
			}	
		}
		
		if(adjCount[u] == 1 && u != neighbor){
			cut = u; break;
		}	
	}
	
	vector<int> res;
	for(int i = 0; i < pohon.size() ; i++){
		if(pohon[i] != cut) res.pb(pohon[i]);
	} 
	res.pb(target);
	nodes[target].tree = res;
	nodes[target].val = nodes[cut].val;
	nodes[target].idx = nodes[cut].idx;

}


int id=0; vector<int> bit; vector<int> firstTree;


void dfsFirst(int idBefore, int idNow){
	
	if(nodes[idNow].visited == 1 || id>=60) return;
	nodes[idNow].visited = 1;
	nodes[idNow].idx = id++;
		nodes[idNow].val = bit[nodes[idNow].idx % 60];
		firstTree.pb(idNow);
		for(int i=0;i<nodes[idNow].adj.size();i++){
		dfsFirst(idNow, nodes[idNow].adj[i]);
		}
		
		nodes[idNow].tree = firstTree;
	
}

void dfs(int idBefore, int idNow){


	if(nodes[idNow].visited == 1) return;
	nodes[idNow].visited = 1;
		bool atFirst = false;
		for(int i=0;i<firstTree.size();i++){
			if(firstTree[i] == idNow) atFirst = true;
		}
		
		if(!atFirst) CopyTree ( idNow, idBefore);
		else nodes[idNow].tree = firstTree;
		for(int i=0;i<nodes[idNow].adj.size();i++){
		dfs(idNow, nodes[idNow].adj[i]);
		}
		
}

int par[10069];
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) {
	
	memset(connected,false,sizeof(connected));
	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])){
		nodes[A[i]].adj.pb(B[i]); nodes[B[i]].adj.pb(A[i]);
		connected[A[i]][B[i]]= true; connected[B[i]][A[i]]= true;
		par[findParent(B[i])] = findParent(A[i]);
		}
	}
	

	//DFS dulu ges di node 0
	dfsFirst(-1,0);
	for(int i=0;i<N;i++) nodes[i].visited=0;
	dfs(-1,0);
	
	

	for(int i=0;i<N;i++){
//		cout<<i<<" : "<<nodes[i].val<<endl;
		MessageBoard(i,nodes[i].val);
	}

}
#include "Ioi.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
 
struct node{
	int idx = -1, visited = 0, val=0;
	vector<int> adj, tree;
} nodes2[10069];
 
 
bool connected2[10069][10069];

void CopyTree2 (int target, int neighbor){
	int adjCount[10069], cut;
	memset(adjCount, 0, sizeof(adjCount));
	
	vector<int> pohon = nodes2[neighbor].tree;
	for(int i = 0; i < pohon.size() ; i++){
		int u = pohon[i];
		for(int j = i+1; j< pohon.size(); j++){
		 	int v = pohon[j];
			if(connected2[u][v]){
				adjCount[u]++; adjCount[v]++;
			}	
		}
		
		if(adjCount[u] == 1 && u != neighbor){
			cut = u; break;
		}	
	}
	
	vector<int> res;
	for(int i = 0; i < pohon.size() ; i++){
		if(pohon[i] != cut) res.pb(pohon[i]);
	} 
	res.pb(target);
	nodes2[target].tree = res;
	nodes2[target].idx = nodes2[cut].idx;
}
 
int id2=0, bit2[60];
vector<int> firstTree2;
void dfsFirst2(int idBefore, int idNow){
	
	if(nodes2[idNow].visited == 1 || id2>=60) return;
	nodes2[idNow].visited = 1;
	nodes2[idNow].idx = id2++;
		firstTree2.pb(idNow);
		for(int i=0;i<nodes2[idNow].adj.size();i++){
		dfsFirst2(idNow, nodes2[idNow].adj[i]);
		}
		
		nodes2[idNow].tree = firstTree2;
	
}
 
int tt=0;
void dfs2(int idBefore, int idNow){


	if(nodes2[idNow].visited == 1) return;
	nodes2[idNow].visited = 1;
		bool atFirst = false;
		for(int i=0;i<firstTree2.size();i++){
			if(firstTree2[i] == idNow) atFirst = true;
		}
		
		if(!atFirst) CopyTree2 ( idNow, idBefore);
		else nodes2[idNow].tree = firstTree2;
		for(int i=0;i<nodes2[idNow].adj.size();i++){
		dfs2(idNow, nodes2[idNow].adj[i]);
		}
		
}
 
 
void solveDFS(int idNow, int bitValue){
	
	nodes2[idNow].visited = 1;
	bit2[nodes2[idNow].idx]= bitValue;
	for(int i=0;i<nodes2[idNow].adj.size();i++){
		int idNext = nodes2[idNow].adj[i];
		if(!nodes2[idNext].visited){
		
		solveDFS(idNext, Move(idNext));
		Move(idNow);
		}
	}
	
}
 
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) {
	
	memset(connected2,false,sizeof(connected2));
	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]);
		connected2[A[i]][B[i]]= true; connected2[B[i]][A[i]]= true;
		par2[findParent2(B[i])] = findParent2(A[i]);
		}
	}
	
	//DFS dulu ges di node 0
	dfsFirst2(-1,0);
	for(int i=0;i<N;i++) nodes2[i].visited=0;
	dfs2(-1,0);
	
	//Solve
	for(int i=0;i<nodes2[P].tree.size();i++) nodes2[nodes2[P].tree[i]].visited=0;
	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 CopyTree(int, int)':
Joi.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Joi.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int j = i+1; j< pohon.size(); j++){
      |                    ~^~~~~~~~~~~~~~
Joi.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 0; i < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Joi.cpp: In function 'void dfsFirst(int, int)':
Joi.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int i=0;i<nodes[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int i=0;i<firstTree.size();i++){
      |               ~^~~~~~~~~~~~~~~~~
Joi.cpp:86:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i=0;i<nodes[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void CopyTree(int, int)':
Joi.cpp:46:3: warning: 'cut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |   if(pohon[i] != cut) res.pb(pohon[i]);
      |   ^~

Ioi.cpp: In function 'void CopyTree2(int, int)':
Ioi.cpp:19:19: 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 < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Ioi.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int j = i+1; j< pohon.size(); j++){
      |                    ~^~~~~~~~~~~~~~
Ioi.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i = 0; i < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfsFirst2(int, int)':
Ioi.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i=0;i<nodes2[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs2(int, int)':
Ioi.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0;i<firstTree2.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~
Ioi.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i=0;i<nodes2[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void solveDFS(int, int)':
Ioi.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i=0;i<nodes2[idNow].adj.size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:117:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for(int i=0;i<nodes2[P].tree.size();i++) nodes2[nodes2[P].tree[i]].visited=0;
      |              ~^~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void CopyTree2(int, int)':
Ioi.cpp:35:3: warning: 'cut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |   if(pohon[i] != cut) res.pb(pohon[i]);
      |   ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 200392 KB Output is correct
2 Correct 78 ms 200388 KB Output is correct
3 Correct 76 ms 200344 KB Output is correct
4 Correct 79 ms 200304 KB Output is correct
5 Correct 91 ms 200380 KB Output is correct
6 Correct 81 ms 200368 KB Output is correct
7 Correct 75 ms 200444 KB Output is correct
8 Correct 80 ms 200484 KB Output is correct
9 Correct 80 ms 200400 KB Output is correct
10 Correct 79 ms 200340 KB Output is correct
11 Correct 82 ms 200568 KB Output is correct
12 Correct 84 ms 200216 KB Output is correct
13 Correct 82 ms 200380 KB Output is correct
14 Correct 78 ms 200376 KB Output is correct
15 Correct 76 ms 200636 KB Output is correct
16 Correct 77 ms 200400 KB Output is correct
17 Correct 78 ms 200424 KB Output is correct
18 Correct 89 ms 200364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 207636 KB Output is correct
2 Correct 259 ms 207808 KB Output is correct
3 Correct 275 ms 207804 KB Output is correct
4 Correct 124 ms 207036 KB Output is correct
5 Correct 135 ms 207272 KB Output is correct
6 Correct 129 ms 207192 KB Output is correct
7 Correct 136 ms 207264 KB Output is correct
8 Correct 131 ms 207324 KB Output is correct
9 Correct 141 ms 207356 KB Output is correct
10 Correct 364 ms 207152 KB Output is correct
11 Correct 382 ms 207020 KB Output is correct
12 Correct 132 ms 206248 KB Output is correct
13 Correct 137 ms 206404 KB Output is correct
14 Correct 131 ms 206624 KB Output is correct
15 Correct 132 ms 206816 KB Output is correct
16 Correct 138 ms 206928 KB Output is correct
17 Correct 141 ms 207076 KB Output is correct
18 Correct 145 ms 206932 KB Output is correct
19 Correct 129 ms 206984 KB Output is correct
20 Correct 123 ms 207456 KB Output is correct
21 Correct 124 ms 207284 KB Output is correct
22 Correct 140 ms 207076 KB Output is correct
23 Correct 141 ms 207336 KB Output is correct
24 Correct 130 ms 207232 KB Output is correct
25 Correct 138 ms 207280 KB Output is correct
26 Correct 131 ms 207352 KB Output is correct
27 Correct 137 ms 207348 KB Output is correct
28 Correct 181 ms 207380 KB Output is correct
29 Correct 131 ms 206708 KB Output is correct
30 Correct 138 ms 206888 KB Output is correct
31 Correct 83 ms 200312 KB Output is correct
32 Correct 84 ms 200368 KB Output is correct
33 Correct 82 ms 200580 KB Output is correct
34 Correct 82 ms 200404 KB Output is correct
35 Correct 84 ms 200340 KB Output is correct
36 Correct 82 ms 200244 KB Output is correct
37 Correct 79 ms 200296 KB Output is correct
38 Correct 78 ms 200356 KB Output is correct
39 Correct 82 ms 200332 KB Output is correct
40 Correct 81 ms 200360 KB Output is correct
41 Correct 75 ms 200396 KB Output is correct
42 Correct 82 ms 200292 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 200356 KB Output is correct
2 Correct 86 ms 200356 KB Output is correct
3 Correct 89 ms 200316 KB Output is correct
4 Correct 81 ms 201516 KB Output is correct
5 Correct 79 ms 201488 KB Output is correct
6 Correct 82 ms 201408 KB Output is correct
7 Correct 80 ms 201632 KB Output is correct
8 Correct 80 ms 201448 KB Output is correct
9 Correct 146 ms 207700 KB Output is correct
10 Correct 128 ms 207836 KB Output is correct
11 Correct 115 ms 207772 KB Output is correct
12 Correct 76 ms 200284 KB Output is correct
13 Correct 79 ms 200316 KB Output is correct
14 Correct 80 ms 200344 KB Output is correct
15 Correct 78 ms 200116 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 207864 KB Output is correct
2 Correct 267 ms 207792 KB Output is correct
3 Correct 251 ms 207840 KB Output is correct
4 Correct 122 ms 207076 KB Output is correct
5 Correct 127 ms 207560 KB Output is correct
6 Correct 145 ms 207328 KB Output is correct
7 Correct 138 ms 207348 KB Output is correct
8 Correct 132 ms 207048 KB Output is correct
9 Correct 138 ms 207316 KB Output is correct
10 Correct 374 ms 207044 KB Output is correct
11 Correct 369 ms 206964 KB Output is correct
12 Correct 122 ms 206308 KB Output is correct
13 Correct 119 ms 206312 KB Output is correct
14 Correct 144 ms 206684 KB Output is correct
15 Correct 133 ms 206940 KB Output is correct
16 Correct 149 ms 207228 KB Output is correct
17 Correct 153 ms 207040 KB Output is correct
18 Correct 124 ms 206936 KB Output is correct
19 Correct 128 ms 206852 KB Output is correct
20 Correct 135 ms 207392 KB Output is correct
21 Correct 118 ms 207356 KB Output is correct
22 Correct 136 ms 207256 KB Output is correct
23 Correct 159 ms 207324 KB Output is correct
24 Correct 129 ms 207196 KB Output is correct
25 Correct 153 ms 207304 KB Output is correct
26 Correct 145 ms 207352 KB Output is correct
27 Correct 140 ms 207436 KB Output is correct
28 Correct 154 ms 207236 KB Output is correct
29 Correct 138 ms 206692 KB Output is correct
30 Correct 143 ms 206964 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 207688 KB Output is correct
2 Correct 267 ms 207784 KB Output is correct
3 Correct 281 ms 207812 KB Output is correct
4 Correct 146 ms 206920 KB Output is correct
5 Correct 143 ms 207740 KB Output is correct
6 Correct 145 ms 207276 KB Output is correct
7 Correct 145 ms 207120 KB Output is correct
8 Correct 136 ms 207316 KB Output is correct
9 Correct 128 ms 207340 KB Output is correct
10 Correct 366 ms 206916 KB Output is correct
11 Correct 365 ms 207060 KB Output is correct
12 Correct 138 ms 206280 KB Output is correct
13 Correct 133 ms 206340 KB Output is correct
14 Correct 167 ms 206560 KB Output is correct
15 Correct 145 ms 207032 KB Output is correct
16 Correct 136 ms 207008 KB Output is correct
17 Correct 137 ms 207004 KB Output is correct
18 Correct 141 ms 206864 KB Output is correct
19 Correct 132 ms 206936 KB Output is correct
20 Correct 133 ms 207496 KB Output is correct
21 Correct 131 ms 207284 KB Output is correct
22 Correct 177 ms 207252 KB Output is correct
23 Correct 148 ms 207184 KB Output is correct
24 Correct 143 ms 207264 KB Output is correct
25 Correct 149 ms 207192 KB Output is correct
26 Correct 145 ms 207108 KB Output is correct
27 Correct 144 ms 207452 KB Output is correct
28 Correct 148 ms 207276 KB Output is correct
29 Correct 147 ms 206724 KB Output is correct
30 Correct 168 ms 206920 KB Output is correct
31 Correct 80 ms 200484 KB Output is correct
32 Correct 79 ms 200392 KB Output is correct
33 Correct 82 ms 200720 KB Output is correct
34 Correct 88 ms 200624 KB Output is correct
35 Correct 83 ms 200332 KB Output is correct
36 Correct 82 ms 200360 KB Output is correct
37 Correct 86 ms 200364 KB Output is correct
38 Correct 103 ms 200368 KB Output is correct
39 Correct 96 ms 200112 KB Output is correct
40 Correct 109 ms 200336 KB Output is correct
41 Correct 83 ms 200356 KB Output is correct
42 Correct 80 ms 200364 KB Output is correct