Submission #122942

#	Time	Username	Problem	Language	Result	Execution time	Memory
122942		onjo0127	Amusement Park (JOI17_amusement_park)	C++17	0 / 100	24 ms	3176 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct TREE {
	vector<pii> edge;
	
	int getleaf(int x) {
		map<int, int> deg;
		for(auto& it: edge) {
			int x, y; tie(x, y) = it;
			++deg[x]; ++deg[y];
		}
		int ret = -1;
		for(auto& it: deg) if(it.second == 1 && it.first != x) ret = it.first;
		return ret;
	}
};

static TREE change(TREE T, int d, int a, int b) {
	TREE ret;
	for(auto& it: T.edge) if(it.first != d && it.second != d) ret.edge.push_back(it);
	ret.edge.push_back({a, b});
	return ret;
}

static TREE T[10009];
static int sid[10009], num[10009], c = 1;
static vector<int> adj[10009];
static bool vs[10009];

static int bit = 61;

static int d = 0;
static void dfs(int x) {
	num[x] = d++; sid[x] = 1; vs[x] = 1;
	for(auto& it: adj[x]) if(!vs[it] && d < bit) {
		T[1].edge.push_back({x, it});
		dfs(it);
	}
}

static void go(int x, int p) {
	vs[x] = 1;
	if(sid[x] == 0) {
		sid[x] = ++c;
		int del = T[sid[p]].getleaf(p);
		num[x] = num[del];
		T[c] = change(T[sid[p]], del, p, x);
	}
	for(auto& it: adj[x]) if(!vs[it]) go(it, x);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	for(int i=0; i<N; i++) MessageBoard(i, (X >> (i%60)) & 1);
	return ;
	for(int i=0; i<M; i++) {
		int u = A[i], v = B[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(0);
	memset(vs, 0, sizeof(vs));
	go(0, 0);
	for(int i=0; i<N; i++) {
		// printf("i: %d, sid: %d, num: %d\n", i, sid[i], num[i]);
		MessageBoard(i, (X >> num[i]) & 1);
	}
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct TREE {
	vector<pii> edge;
	
	int getleaf(int x) {
		map<int, int> deg;
		for(auto& it: edge) {
			int x, y; tie(x, y) = it;
			++deg[x]; ++deg[y];
		}
		int ret = -1;
		for(auto& it: deg) if(it.second == 1 && it.first != x) ret = it.first;
		return ret;
	}
};

static TREE change(TREE T, int d, int a, int b) {
	TREE ret;
	for(auto& it: T.edge) if(it.first != d && it.second != d) ret.edge.push_back(it);
	ret.edge.push_back({a, b});
	return ret;
}

static TREE T[10009];
static int sid[10009], num[10009], c = 1;
static vector<int> adj[10009];
static bool vs[10009];

static int bit = 61;

static int d = 0;
static void dfs(int x) {
	num[x] = d++; sid[x] = 1; vs[x] = 1;
	for(auto& it: adj[x]) if(!vs[it] && d < bit) {
		T[1].edge.push_back({x, it});
		dfs(it);
	}
}

static void go(int x, int p) {
	vs[x] = 1;
	if(sid[x] == 0) {
		sid[x] = ++c;
		int del = T[sid[p]].getleaf(p);
		num[x] = num[del];
		T[c] = change(T[sid[p]], del, p, x);
	}
	for(auto& it: adj[x]) if(!vs[it]) go(it, x);
}

static long long ret;
static bool vis[10009];

static void getans(int tid, int now, int x, int par) {
	// printf("tid: %d, now: %d, x: %d, par: %d, num[now]: %d\n", tid, now, x, par, num[now]);
	vis[now] = 1;
	ret |= (x << num[now]);
	for(auto& it: T[tid].edge) {
		int u, v; tie(u, v) = it;
		if(v == now) swap(u, v);
		if(u == now && !vis[v]) getans(tid, v, Move(v), now);
	}
	if(par != -1) Move(par);
}

static int move(int x) {
	// printf("dest: %d\n", x);
	return Move(x);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	int xx;
	while(P % 60 || P + 60 > N) xx = move(--P);
	for(int i=0; i<60; i++) {
		ret |= (xx << i);
		if(i+1 < 60) xx = move(++P);
	}
	return ret;

	for(int i=0; i<M; i++) {
		int u = A[i], v = B[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(0);
	memset(vs, 0, sizeof(vs));
	go(0, 0);
	getans(sid[P], P, V, -1);
	return ret;
}

Compilation message (stderr)

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:79:14: warning: 'xx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ret |= (xx << i);
          ~~~~^~~~~

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