Submission #339389

#	Time	Username	Problem	Language	Result	Execution time	Memory
339389		nandonathaniel	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	306 ms	34900 KiB

Joi

#include "Joi.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN2=10005;
vector<int> adj[MAXN2],tree[MAXN2],urutan;
bool visited[MAXN2];
int warna[MAXN2],par[MAXN2],deg[MAXN2],ya[MAXN2];
bitset<MAXN2> mat[MAXN2];
 
void spanningTreeD(){
	par[0]=-1;
	visited[0]=true;
	queue<int> Q;
	Q.push(0);
	while(!Q.empty()){
		int now=Q.front();
		Q.pop();
		urutan.push_back(now);
		for(auto nxt : adj[now]){
			if(visited[nxt])continue;
			visited[nxt]=true;
			par[nxt]=now;
			mat[now][nxt]=1;
			mat[nxt][now]=1;
			Q.push(nxt);
		}
	}
}
 
void buildTreeD(int now){
	int rt=par[now];
	memset(deg,0,sizeof(deg));
	for(auto isi : tree[rt]){
		for(auto isi2 : tree[rt]){
			if(isi<isi2 && mat[isi][isi2]){
				deg[isi]++;
				deg[isi2]++;
			}
		}
	}
	int ganti;
	for(auto isi : tree[rt]){
		if(isi==rt)continue;
		if(deg[isi]==1){
			ganti=isi;
			break;
		}
	}
	for(auto isi : tree[rt]){
		deg[isi]=0;
		if(isi!=ganti)tree[now].push_back(isi);
	}
	tree[now].push_back(now);
	warna[now]=warna[ganti];
}
 
void Joi(int N, int M, int A[], int B[], long long X,
              int T) {
	for(int i=0;i<M;i++){
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	for(int i=0;i<60;i++){
		if(X & (1LL<<i))ya[i]=1;
	}
	spanningTreeD();
	vector<int> awal;
	for(int i=0;i<60;i++){
		awal.push_back(urutan[i]);
		warna[urutan[i]]=i;
	}
	for(int i=0;i<60;i++)tree[urutan[i]]=awal;
	for(int i=60;i<N;i++)buildTreeD(urutan[i]);
	for(int i=0;i<N;i++){
		MessageBoard(i,ya[warna[i]]);
	}
}

Ioi

#include "Ioi.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN=10005;
vector<int> adj2[MAXN],tree2[MAXN],urutan2;
bool visited2[MAXN];
int warna2[MAXN],par2[MAXN],deg2[MAXN],jaw[MAXN];
bitset<MAXN> mat2[MAXN];
bool subtree[MAXN];
 
void spanningTreeC(){
	par2[0]=-1;
	visited2[0]=true;
	queue<int> Q;
	Q.push(0);
	while(!Q.empty()){
		int now=Q.front();
		Q.pop();
		urutan2.push_back(now);
		for(auto nxt : adj2[now]){
			if(visited2[nxt])continue;
			visited2[nxt]=true;
			par2[nxt]=now;
			mat2[now][nxt]=1;
			mat2[nxt][now]=1;
			Q.push(nxt);
		}
	}
}
 
void buildTreeC(int now){
	int rt=par2[now];
	memset(deg2,0,sizeof(deg2));
	for(auto isi : tree2[rt]){
		for(auto isi2 : tree2[rt]){
			if(isi<isi2 && mat2[isi][isi2]){
				deg2[isi]++;
				deg2[isi2]++;
			}
		}
	}
	int ganti;
	for(auto isi : tree2[rt]){
		if(isi==rt)continue;
		if(deg2[isi]==1){
			ganti=isi;
			break;
		}
	}
	for(auto isi : tree2[rt]){
		deg2[isi]=0;
		if(isi!=ganti)tree2[now].push_back(isi);
	}
	tree2[now].push_back(now);
	warna2[now]=warna2[ganti];
}
 
void dfs(int now,int stat){
	jaw[warna2[now]]=stat;
	visited2[now]=true;
	for(auto nxt : adj2[now]){
		if(visited2[nxt])continue;
		if(!subtree[nxt])continue;
		if(!mat2[now][nxt])continue;
		dfs(nxt,Move(nxt));
		Move(now);
	}
}
 
long long Ioi(int N, int M, int A[], int B[],
                     int P, int V, int T) {
	for(int i=0;i<M;i++){
		adj2[A[i]].push_back(B[i]);
		adj2[B[i]].push_back(A[i]);
	}
	spanningTreeC();
	vector<int> awal;
	for(int i=0;i<60;i++){
		awal.push_back(urutan2[i]);
		warna2[urutan2[i]]=i;
	}
	for(int i=0;i<60;i++)tree2[urutan2[i]]=awal;
	for(int i=60;i<N;i++)buildTreeC(urutan2[i]);
	for(auto isi : tree2[P])subtree[isi]=true;
	memset(visited2,false,sizeof(visited2));
	dfs(P,V);
	long long ans=0;
	for(int i=0;i<60;i++){
		if(jaw[i])ans+=(1LL<<i);
	}
	return ans;
}

Compilation message (stderr)

Joi.cpp: In function 'void buildTreeD(int)':
Joi.cpp:51:3: warning: 'ganti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |   if(isi!=ganti)tree[now].push_back(isi);
      |   ^~

Ioi.cpp: In function 'void buildTreeC(int)':
Ioi.cpp:52:3: warning: 'ganti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |   if(isi!=ganti)tree2[now].push_back(isi);
      |   ^~

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