oj.uz

Submission #710687

# Submission time Handle Problem Language Result Execution time Memory
710687 2023-03-15T15:29:30 Z dum123 Amusement Park (JOI17_amusement_park) C++14
0 / 100
 38 ms 21260 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){
	
	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[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;
	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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17944 KB Output is correct
2 Correct 9 ms 17944 KB Output is correct
3 Correct 10 ms 17948 KB Output is correct
4 Correct 9 ms 17940 KB Output is correct
5 Correct 10 ms 17936 KB Output is correct
6 Correct 11 ms 18068 KB Output is correct
7 Correct 9 ms 17868 KB Output is correct
8 Correct 9 ms 17888 KB Output is correct
9 Correct 9 ms 17948 KB Output is correct
10 Correct 9 ms 17944 KB Output is correct
11 Incorrect 12 ms 18120 KB Wrong Answer [7]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 21260 KB Output is correct
2 Correct 30 ms 21248 KB Output is correct
3 Incorrect 35 ms 21112 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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