oj.uz

Submission #710677

# Submission time Handle Problem Language Result Execution time Memory
710677 2023-03-15T15:10:28 Z dum123 Amusement Park (JOI17_amusement_park) C++14
0 / 100
 39 ms 22296 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[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){
	node2 now= nodes2[idNow];
	if(nodes2[idNow].visited) return;
	nodes2[idNow].visited=1;


	nodes2[idNow].idx = id2++;
//	cout<<idNow<<" "<<nodes2[idNow].idx<<endl;
	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;
				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 && !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[A[i]] = findParent2(B[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;
//	cout<<endl;
	for(int i=0;i<60;i++){
//		cout<<bit2[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:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<nodes2[idNow].adj.size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void solveDFS(int, int)':
Ioi.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(int i=0;i<now.adj.size();i++){
      |                ~^~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17904 KB Output is correct
2 Correct 10 ms 17940 KB Output is correct
3 Correct 11 ms 17884 KB Output is correct
4 Correct 11 ms 17940 KB Output is correct
5 Correct 12 ms 17924 KB Output is correct
6 Correct 10 ms 17948 KB Output is correct
7 Correct 10 ms 17864 KB Output is correct
8 Correct 10 ms 17956 KB Output is correct
9 Correct 10 ms 17952 KB Output is correct
10 Correct 11 ms 17908 KB Output is correct
11 Incorrect 13 ms 18276 KB Wrong Answer [7]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 21736 KB Output is correct
2 Correct 38 ms 22296 KB Output is correct
3 Incorrect 39 ms 22272 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 21836 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 21896 KB Output isn't correct
2 Halted 0 ms 0 KB -