oj.uz

Submission #710696

# Submission time Handle Problem Language Result Execution time Memory
710696 2023-03-15T15:39:23 Z dum123 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 260 ms 21436 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[findParent(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 & bit2[now.idx % 60] == -1){
	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 && bit2[nodes2[now.adj[i]].idx % 60] == -1) {
					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[findParent2(B[i])] = findParent2(A[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:30:49: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   30 |  if(!nodes2[idNow].counted & bit2[now.idx % 60] == -1){
      |                              ~~~~~~~~~~~~~~~~~~~^~~~~
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 Incorrect 10 ms 17944 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 19824 KB Output is correct
2 Incorrect 154 ms 19732 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17992 KB Output is correct
2 Correct 9 ms 17932 KB Output is correct
3 Correct 10 ms 17936 KB Output is correct
4 Correct 13 ms 18352 KB Output is correct
5 Correct 14 ms 18348 KB Output is correct
6 Correct 12 ms 18408 KB Output is correct
7 Correct 12 ms 18336 KB Output is correct
8 Correct 12 ms 18356 KB Output is correct
9 Correct 19 ms 21436 KB Output is correct
10 Correct 18 ms 21364 KB Output is correct
11 Correct 22 ms 21320 KB Output is correct
12 Correct 11 ms 17936 KB Output is correct
13 Correct 10 ms 17940 KB Output is correct
14 Correct 11 ms 17940 KB Output is correct
15 Correct 9 ms 17936 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 19912 KB Output is correct
2 Correct 160 ms 19876 KB Output is correct
3 Correct 162 ms 19864 KB Output is correct
4 Correct 23 ms 19252 KB Output is correct
5 Correct 22 ms 20872 KB Output is correct
6 Correct 20 ms 20164 KB Output is correct
7 Correct 22 ms 20040 KB Output is correct
8 Correct 22 ms 19768 KB Output is correct
9 Correct 25 ms 19920 KB Output is correct
10 Correct 260 ms 19608 KB Output is correct
11 Incorrect 257 ms 19520 KB Wrong Answer [7]
12 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 19864 KB Output is correct
2 Incorrect 160 ms 19844 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -