Submission #711762

#	Time	Username	Problem	Language	Result	Execution time	Memory
711762		dum123	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	382 ms	207864 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;
	nodes[target].idx = nodes[cut].idx;

}


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);
		else nodes[idNow].tree = firstTree;
		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,false,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]]= true; connected[B[i]][A[i]]= true;
		par[findParent(B[i])] = findParent(A[i]);
		}
	}
	

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

	for(int i=0;i<N;i++){
//		cout<<i<<" : "<<nodes[i].val<<endl;
		MessageBoard(i,nodes[i].val);
	}

}

Ioi

#include "Ioi.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;
} nodes2[10069];
 
 
bool connected2[10069][10069];

void CopyTree2 (int target, int neighbor){
	int adjCount[10069], cut;
	memset(adjCount, 0, sizeof(adjCount));
	
	vector<int> pohon = nodes2[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(connected2[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);
	nodes2[target].tree = res;
	nodes2[target].idx = nodes2[cut].idx;
}
 
int id2=0, bit2[60];
vector<int> firstTree2;
void dfsFirst2(int idBefore, int idNow){
	
	if(nodes2[idNow].visited == 1 || id2>=60) return;
	nodes2[idNow].visited = 1;
	nodes2[idNow].idx = id2++;
		firstTree2.pb(idNow);
		for(int i=0;i<nodes2[idNow].adj.size();i++){
		dfsFirst2(idNow, nodes2[idNow].adj[i]);
		}
		
		nodes2[idNow].tree = firstTree2;
	
}
 
int tt=0;
void dfs2(int idBefore, int idNow){


	if(nodes2[idNow].visited == 1) return;
	nodes2[idNow].visited = 1;
		bool atFirst = false;
		for(int i=0;i<firstTree2.size();i++){
			if(firstTree2[i] == idNow) atFirst = true;
		}
		
		if(!atFirst) CopyTree2 ( idNow, idBefore);
		else nodes2[idNow].tree = firstTree2;
		for(int i=0;i<nodes2[idNow].adj.size();i++){
		dfs2(idNow, nodes2[idNow].adj[i]);
		}
		
}
 
 
void solveDFS(int idNow, int bitValue){
	
	nodes2[idNow].visited = 1;
	bit2[nodes2[idNow].idx]= bitValue;
	for(int i=0;i<nodes2[idNow].adj.size();i++){
		int idNext = nodes2[idNow].adj[i];
		if(!nodes2[idNext].visited){
		
		solveDFS(idNext, Move(idNext));
		Move(idNow);
		}
	}
	
}
 
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) {
	
	memset(connected2,false,sizeof(connected2));
	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]);
		connected2[A[i]][B[i]]= true; connected2[B[i]][A[i]]= true;
		par2[findParent2(B[i])] = findParent2(A[i]);
		}
	}
	
	//DFS dulu ges di node 0
	dfsFirst2(-1,0);
	for(int i=0;i<N;i++) nodes2[i].visited=0;
	dfs2(-1,0);
	
	//Solve
	for(int i=0;i<nodes2[P].tree.size();i++) nodes2[nodes2[P].tree[i]].visited=0;
	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 (stderr)

Joi.cpp: In function 'void CopyTree(int, int)':
Joi.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Joi.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int j = i+1; j< pohon.size(); j++){
      |                    ~^~~~~~~~~~~~~~
Joi.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 0; i < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Joi.cpp: In function 'void dfsFirst(int, int)':
Joi.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int i=0;i<nodes[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int i=0;i<firstTree.size();i++){
      |               ~^~~~~~~~~~~~~~~~~
Joi.cpp:86:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i=0;i<nodes[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void CopyTree(int, int)':
Joi.cpp:46:3: warning: 'cut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |   if(pohon[i] != cut) res.pb(pohon[i]);
      |   ^~

Ioi.cpp: In function 'void CopyTree2(int, int)':
Ioi.cpp:19:19: 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 < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Ioi.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int j = i+1; j< pohon.size(); j++){
      |                    ~^~~~~~~~~~~~~~
Ioi.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i = 0; i < pohon.size() ; i++){
      |                 ~~^~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfsFirst2(int, int)':
Ioi.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i=0;i<nodes2[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs2(int, int)':
Ioi.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0;i<firstTree2.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~
Ioi.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i=0;i<nodes2[idNow].adj.size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void solveDFS(int, int)':
Ioi.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i=0;i<nodes2[idNow].adj.size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:117:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for(int i=0;i<nodes2[P].tree.size();i++) nodes2[nodes2[P].tree[i]].visited=0;
      |              ~^~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void CopyTree2(int, int)':
Ioi.cpp:35:3: warning: 'cut' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |   if(pohon[i] != cut) res.pb(pohon[i]);
      |   ^~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17