제출 #711502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711502		dum123	Amusement Park (JOI17_amusement_park)	C++14	0 / 100	191 ms	112184 KiB

Joi

#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;
}

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(connected[u][v]){
				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;

}


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);

		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,0,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]]= 1; connected[B[i]][A[i]]= 1;
		par[findParent(B[i])] = findParent(A[i]);
		}
	}
	

	//DFS dulu ges di node 0
	dfsFirst(-1,0);
	
	
	
	for(int i=0;i<N;i++){
		MessageBoard(i,nodes[i].val);
	}

}

Ioi

#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]);
	}
}

int tt=0;
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(tt==3) if(bit2[nodes2[idNow].idx %60] != -1) return;
	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) {
					if(tt==3) if(bit2[nodes2[now.adj[i]].idx %60] != -1) 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){
		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
	tt=T;
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

Joi.cpp: In function 'void CopyTree(int, int)':
Joi.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0; i < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Joi.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int j = i+1; j< pohon.size(); j++){
      |                    ~^~~~~~~~~~~~~~
Joi.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i = 0; i < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Joi.cpp: In function 'void dfsFirst(int, int)':
Joi.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i=0;i<nodes[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i=0;i<firstTree.size();i++){
      |               ~^~~~~~~~~~~~~~~~~
Joi.cpp:83:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int i=0;i<nodes[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void CopyTree(int, int)':
Joi.cpp:45:3: warning: 'cut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |   if(pohon[i] != cut) res.pb(pohon[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: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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17