oj.uz

Submission #122853

# Submission time Handle Problem Language Result Execution time Memory
122853 2019-06-29T11:22:17 Z sebinkim Amusement Park (JOI17_amusement_park) C++14
0 / 100
 65 ms 14912 KB 
#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);
	}
}
#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, 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

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:64:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<E[p].size(); i++){
            ~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2396 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 14912 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2288 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 14848 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 14912 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -