oj.uz

Submission #122948

# Submission time Handle Problem Language Result Execution time Memory
122948 2019-06-29T15:40:26 Z onjo0127 Amusement Park (JOI17_amusement_park) C++14
0 / 100
 130 ms 9792 KB 
#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);
	}
}

#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 |= ((1LL*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);
}

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) {
	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;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1648 KB Output is correct
2 Correct 4 ms 1920 KB Output is correct
3 Incorrect 4 ms 1904 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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