oj.uz

Submission #710674

# Submission time Handle Problem Language Result Execution time Memory
710674 2023-03-15T14:58:17 Z dum123 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 34 ms 20908 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;
	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(bit2[now.idx % 60] == -1){
			bit2[now.idx % 60] = bitInside;
//			cout<<now.idx<<" "<<bit2[idNow]<<endl;
			countt2++;
			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 && bit2[nodes2[now.before].idx % 60] == -1){
//		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:36:17: 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<now.adj.size();i++){
      |                ~^~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16400 KB Output is correct
2 Correct 9 ms 16316 KB Output is correct
3 Correct 9 ms 16412 KB Output is correct
4 Correct 10 ms 16964 KB Output is correct
5 Correct 10 ms 16948 KB Output is correct
6 Correct 9 ms 16948 KB Output is correct
7 Correct 11 ms 16932 KB Output is correct
8 Correct 11 ms 16968 KB Output is correct
9 Correct 22 ms 20824 KB Output is correct
10 Correct 19 ms 20908 KB Output is correct
11 Correct 19 ms 20904 KB Output is correct
12 Correct 9 ms 16404 KB Output is correct
13 Correct 9 ms 16412 KB Output is correct
14 Correct 9 ms 16404 KB Output is correct
15 Correct 10 ms 16408 KB Output is correct

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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