oj.uz

Submission #715524

# Submission time Handle Problem Language Result Execution time Memory
715524 2023-03-27T06:53:16 Z dum123 Amusement Park (JOI17_amusement_park) C++14
100 / 100
 326 ms 12328 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;
}

set <int> con[10069];
//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(con[u].find(v)!= con[u].end()){
				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;
		con[A[i]].insert(B[i]); con[B[i]].insert(A[i]);
		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];
 
set <int> con2[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(con2[u].find(v) != con2[u].end()){
				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;
		con2[A[i]].insert(B[i]); con2[B[i]].insert(A[i]);
		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:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Joi.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j = i+1; j< pohon.size(); j++){
      |                    ~^~~~~~~~~~~~~~
Joi.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 0; i < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Joi.cpp: In function 'void dfsFirst(int, int)':
Joi.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int i=0;i<nodes[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:81:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int i=0;i<firstTree.size();i++){
      |               ~^~~~~~~~~~~~~~~~~
Joi.cpp:87:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int i=0;i<nodes[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void CopyTree(int, int)':
Joi.cpp:52:33: warning: 'cut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |  nodes[target].idx = nodes[cut].idx;
      |                      ~~~~~~~~~~~^~~

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:118:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  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:39:35: warning: 'cut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |  nodes2[target].idx = nodes2[cut].idx;
      |                       ~~~~~~~~~~~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3080 KB Output is correct
2 Correct 2 ms 3080 KB Output is correct
3 Correct 4 ms 3156 KB Output is correct
4 Correct 2 ms 3012 KB Output is correct
5 Correct 2 ms 3072 KB Output is correct
6 Correct 4 ms 3080 KB Output is correct
7 Correct 6 ms 3076 KB Output is correct
8 Correct 4 ms 3076 KB Output is correct
9 Correct 4 ms 3100 KB Output is correct
10 Correct 2 ms 3072 KB Output is correct
11 Correct 8 ms 3268 KB Output is correct
12 Correct 2 ms 2824 KB Output is correct
13 Correct 4 ms 3076 KB Output is correct
14 Correct 4 ms 3088 KB Output is correct
15 Correct 5 ms 3172 KB Output is correct
16 Correct 4 ms 3076 KB Output is correct
17 Correct 3 ms 3120 KB Output is correct
18 Correct 4 ms 3076 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 11772 KB Output is correct
2 Correct 221 ms 12208 KB Output is correct
3 Correct 270 ms 12184 KB Output is correct
4 Correct 79 ms 11476 KB Output is correct
5 Correct 64 ms 11772 KB Output is correct
6 Correct 62 ms 11624 KB Output is correct
7 Correct 71 ms 11680 KB Output is correct
8 Correct 87 ms 11676 KB Output is correct
9 Correct 66 ms 11756 KB Output is correct
10 Correct 318 ms 11560 KB Output is correct
11 Correct 295 ms 11488 KB Output is correct
12 Correct 88 ms 10692 KB Output is correct
13 Correct 90 ms 10528 KB Output is correct
14 Correct 75 ms 11024 KB Output is correct
15 Correct 90 ms 11320 KB Output is correct
16 Correct 100 ms 11316 KB Output is correct
17 Correct 75 ms 11544 KB Output is correct
18 Correct 98 ms 11392 KB Output is correct
19 Correct 76 ms 11544 KB Output is correct
20 Correct 55 ms 11736 KB Output is correct
21 Correct 52 ms 11688 KB Output is correct
22 Correct 70 ms 11596 KB Output is correct
23 Correct 65 ms 11736 KB Output is correct
24 Correct 64 ms 11504 KB Output is correct
25 Correct 68 ms 11696 KB Output is correct
26 Correct 78 ms 11800 KB Output is correct
27 Correct 63 ms 11776 KB Output is correct
28 Correct 64 ms 11784 KB Output is correct
29 Correct 64 ms 10892 KB Output is correct
30 Correct 72 ms 11220 KB Output is correct
31 Correct 3 ms 3076 KB Output is correct
32 Correct 3 ms 3076 KB Output is correct
33 Correct 4 ms 3084 KB Output is correct
34 Correct 3 ms 3076 KB Output is correct
35 Correct 3 ms 3008 KB Output is correct
36 Correct 3 ms 3088 KB Output is correct
37 Correct 2 ms 3076 KB Output is correct
38 Correct 2 ms 2996 KB Output is correct
39 Correct 3 ms 2828 KB Output is correct
40 Correct 3 ms 3072 KB Output is correct
41 Correct 2 ms 3076 KB Output is correct
42 Correct 2 ms 3032 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3072 KB Output is correct
2 Correct 2 ms 3036 KB Output is correct
3 Correct 3 ms 3084 KB Output is correct
4 Correct 11 ms 4408 KB Output is correct
5 Correct 9 ms 4456 KB Output is correct
6 Correct 10 ms 4464 KB Output is correct
7 Correct 10 ms 4468 KB Output is correct
8 Correct 9 ms 4400 KB Output is correct
9 Correct 52 ms 12252 KB Output is correct
10 Correct 49 ms 12136 KB Output is correct
11 Correct 47 ms 12192 KB Output is correct
12 Correct 3 ms 3084 KB Output is correct
13 Correct 2 ms 3084 KB Output is correct
14 Correct 2 ms 2828 KB Output is correct
15 Correct 2 ms 2828 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 11800 KB Output is correct
2 Correct 210 ms 12228 KB Output is correct
3 Correct 203 ms 12200 KB Output is correct
4 Correct 68 ms 11300 KB Output is correct
5 Correct 69 ms 12004 KB Output is correct
6 Correct 75 ms 11720 KB Output is correct
7 Correct 67 ms 11736 KB Output is correct
8 Correct 72 ms 11552 KB Output is correct
9 Correct 63 ms 11668 KB Output is correct
10 Correct 308 ms 11516 KB Output is correct
11 Correct 319 ms 11608 KB Output is correct
12 Correct 86 ms 10688 KB Output is correct
13 Correct 61 ms 10668 KB Output is correct
14 Correct 75 ms 10900 KB Output is correct
15 Correct 82 ms 11424 KB Output is correct
16 Correct 103 ms 11440 KB Output is correct
17 Correct 75 ms 11452 KB Output is correct
18 Correct 78 ms 11452 KB Output is correct
19 Correct 111 ms 11444 KB Output is correct
20 Correct 53 ms 11780 KB Output is correct
21 Correct 52 ms 11640 KB Output is correct
22 Correct 64 ms 11784 KB Output is correct
23 Correct 67 ms 11668 KB Output is correct
24 Correct 61 ms 11780 KB Output is correct
25 Correct 64 ms 11716 KB Output is correct
26 Correct 64 ms 11784 KB Output is correct
27 Correct 73 ms 11824 KB Output is correct
28 Correct 68 ms 11648 KB Output is correct
29 Correct 58 ms 10880 KB Output is correct
30 Correct 67 ms 11356 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 11840 KB Output is correct
2 Correct 208 ms 12328 KB Output is correct
3 Correct 263 ms 12212 KB Output is correct
4 Correct 80 ms 11484 KB Output is correct
5 Correct 71 ms 12136 KB Output is correct
6 Correct 74 ms 11784 KB Output is correct
7 Correct 75 ms 11588 KB Output is correct
8 Correct 68 ms 11808 KB Output is correct
9 Correct 64 ms 11840 KB Output is correct
10 Correct 326 ms 11456 KB Output is correct
11 Correct 300 ms 11448 KB Output is correct
12 Correct 72 ms 10608 KB Output is correct
13 Correct 75 ms 10668 KB Output is correct
14 Correct 77 ms 11152 KB Output is correct
15 Correct 101 ms 11344 KB Output is correct
16 Correct 101 ms 11440 KB Output is correct
17 Correct 123 ms 11484 KB Output is correct
18 Correct 93 ms 11444 KB Output is correct
19 Correct 84 ms 11380 KB Output is correct
20 Correct 56 ms 11912 KB Output is correct
21 Correct 52 ms 11812 KB Output is correct
22 Correct 63 ms 11756 KB Output is correct
23 Correct 63 ms 11700 KB Output is correct
24 Correct 70 ms 11688 KB Output is correct
25 Correct 63 ms 11648 KB Output is correct
26 Correct 64 ms 11632 KB Output is correct
27 Correct 67 ms 11836 KB Output is correct
28 Correct 77 ms 11728 KB Output is correct
29 Correct 77 ms 11064 KB Output is correct
30 Correct 63 ms 11300 KB Output is correct
31 Correct 3 ms 3076 KB Output is correct
32 Correct 2 ms 3084 KB Output is correct
33 Correct 4 ms 3148 KB Output is correct
34 Correct 3 ms 2996 KB Output is correct
35 Correct 3 ms 3000 KB Output is correct
36 Correct 2 ms 3092 KB Output is correct
37 Correct 2 ms 3084 KB Output is correct
38 Correct 2 ms 3084 KB Output is correct
39 Correct 2 ms 2828 KB Output is correct
40 Correct 3 ms 3000 KB Output is correct
41 Correct 3 ms 3076 KB Output is correct
42 Correct 2 ms 3068 KB Output is correct