Submission #122857

#	Time	Username	Problem	Language	Result	Execution time	Memory
122857		sebinkim	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	62 ms	15048 KiB

Joi

#include <bits/stdc++.h>

#include "Joi.h"

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

static vector <int> V[10101], T[10101], X;
static vector <pii> E[10101];
static int S[10101], C[10101];
static bool vis[10101];
static int cnt;

static void dfs1(int p, int r)
{
	vis[p] = 1;
	
	for(int &t: V[p]){
		if(!vis[t]){
			T[p].push_back(t);
			dfs1(t, p);
		}
	}
}

static void dfs2(int p, int r)
{
	C[p] = cnt;
	if(++cnt == 60) return;
	for(int &t: T[p]){
		E[0].emplace_back(t, p);
		X.push_back(t);
		dfs2(t, p);
		if(cnt == 60) return;
	}
}

static void dfs3(int p, int r)
{
	if(E[p].empty()){
		int i;
		
		E[p] = E[r];
		
		for(pii &e: E[p]){
			S[e.first] = 0; S[e.second] = 0;
		}
		
		for(pii &e: E[p]){
			S[e.first] ++; S[e.second] ++;
		}
		
		for(i=0; i<E[p].size(); i++){
			if(S[E[p][i].first] == 1 && E[p][i].first != r) break;
			if(S[E[p][i].second] == 1 && E[p][i].second != r) break;
		}
		
		if(S[E[p][i].first] == 1) C[p] = C[E[p][i].first];
		else C[p] = C[E[p][i].second];
		
		swap(E[p][i], E[p].back()); E[p].pop_back();
		
		E[p].emplace_back(p, r);
	}
	
	for(int &t: T[p]){
		dfs3(t, p);
	}
}

void Joi(int n, int m, int A[], int B[], ll x, int t)
{
	int i;
	
	for(i=0; i<m; i++){
		V[A[i]].push_back(B[i]);
		V[B[i]].push_back(A[i]);
	}
	
	dfs1(0, 0);
	dfs2(0, 0);
	
	for(int &x: X){
		E[x] = E[0];
	}
	
	dfs3(0, 0);
	
	for(i=0; i<n; i++){
		MessageBoard(i, x & (1ll << C[i])? 1 : 0);
	}
}

Ioi

#include <bits/stdc++.h>

#include "Ioi.h"

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

static vector <int> V[10101], T[10101], X;
static vector <pii> E[10101];
static int S[10101], C[10101];
static bool chk[10101], vis[10101];
static int cnt;
static ll ans;

static void move(int p)
{
	ll v = Move(p);
	if(!chk[p]){
		chk[p] = 1;
		ans += v << C[p];
	}
}

static void dfs1(int p, int r)
{
	vis[p] = 1;
	
	for(int &t: V[p]){
		if(!vis[t]){
			T[p].push_back(t);
			dfs1(t, p);
		}
	}
}

static void dfs2(int p, int r)
{
	C[p] = cnt++;
	if(cnt == 60) return;
	for(int &t: T[p]){
		E[0].emplace_back(t, p);
		X.push_back(t);
		dfs2(t, p);
		if(cnt == 60) return;
	}
}

static void dfs3(int p, int r)
{
	if(E[p].empty()){
		int i;
		
		E[p] = E[r];
		
		for(pii &e: E[p]){
			S[e.first] = 0; S[e.second] = 0;
		}
		
		for(pii &e: E[p]){
			S[e.first] ++; S[e.second] ++;
		}
		
		for(i=0; i<E[p].size(); i++){
			if(S[E[p][i].first] == 1 && E[p][i].first != r) break;
			if(S[E[p][i].second] == 1 && E[p][i].second != r) break;
		}
		
		if(S[E[p][i].first] == 1) C[p] = C[E[p][i].first];
		else C[p] = C[E[p][i].second];
		
		swap(E[p][i], E[p].back()); E[p].pop_back();
		
		E[p].emplace_back(p, r);
	}
	
	for(int &t: T[p]){
		dfs3(t, p);
	}
}

static void dfs4(int p, int r)
{
	for(int &t: T[p]){
		if(t != r){
			move(t);
			dfs4(t, p);
			move(p);
		}
	}
}

ll Ioi(int n, int m, int A[], int B[], int p, int v, int t)
{
	int i;
	
	for(i=0; i<m; i++){
		V[A[i]].push_back(B[i]);
		V[B[i]].push_back(A[i]);
	}
	
	dfs1(0, 0);
	dfs2(0, 0);
	
	for(int &x: X){
		E[x] = E[0];
	}
	
	dfs3(0, 0);
		
	for(i=0; i<n; i++){
		T[i].clear();
	}
	
	for(pii &e: E[p]){
		T[e.first].push_back(e.second);
		T[e.second].push_back(e.first);
	}
		
	dfs4(p, p);
	
	return ans;
}

Compilation message (stderr)

Joi.cpp: In function 'void dfs3(int, int)':
Joi.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<E[p].size(); i++){
            ~^~~~~~~~~~~~

Ioi.cpp: In function 'void dfs3(int, int)':
Ioi.cpp:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<E[p].size(); i++){
            ~^~~~~~~~~~~~

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