oj.uz

답안 #86595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
86595 2018-11-26T20:38:22 Z KCSC Amusement Park (JOI17_amusement_park) C++14
0 / 100
 49 ms 6936 KB 
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 10000;

static int szt[MAXN], psb[MAXN], psl[MAXN], inc[MAXN], fth[MAXN];

static bitset<MAXN> oki;
static vector<int> ied[MAXN], edg[MAXN], lin[MAXN];
/*
#ifdef HOME
int mess[MAXN], _tot, _cr;
set<int> mst;

void MessageBoard(int x, int v) {
	assert(mst.find(x) == mst.end());
	mess[x] = v; mst.insert(x); }

int Move(int x) {
	assert(_cr == fth[x] or find(edg[x].begin(), edg[x].end(), _cr) != edg[x].end()); 
	_cr = x; ++_tot; assert(_tot <= 120);
	return mess[x]; }
#endif
*/
void MessageBoard(int x, int v);

static void dfsJoi1(int x) {
	oki[x] = true; szt[x] = 1;
	sort(ied[x].begin(), ied[x].end());
	for (int y : ied[x]) { if (!oki[y]) { 
		fth[y] = x; dfsJoi1(y); 
		edg[x].push_back(y); szt[x] += szt[y]; } } }

static void dfsJoi3(int x, int c) {
	psl[x] = lin[c].size(); lin[c].push_back(x);
	for (int y : edg[x]) {
		if (inc[y] == c) {
			dfsJoi3(y, c); lin[c].push_back(x); } } }

static int tot;
static void dfsJoi2(int x, long long v) {
	if (szt[x] >= 60 and inc[x] == -1) {	
		vector<int> que(1, x); ++tot;
		for (int i = 0; i < 60; ++i) {
			int cr = que[i]; inc[cr] = tot; 
			psb[cr] = i; 
			if (v > 0) {
				MessageBoard(cr, (v >> psb[cr]) & 1); }
			for (int nx : edg[cr]) { 
				if (que.size() < 60) { 
					que.push_back(nx); } } } 
		dfsJoi3(x, tot); lin[tot].pop_back(); }
	else if (szt[x] < 60 and inc[x] == -1) {
		int nr = 0, ax = x;	
		while (inc[ax] == -1) {
			++nr; ax = fth[ax]; }
		int ps = ((119 - nr) + psl[ax]) % lin[inc[ax]].size(); 
		psb[x] = psb[lin[inc[ax]][ps]];
		if (v > 0) {
			MessageBoard(x, (v >> psb[x]) & 1); } 
	} 
	for (int y : edg[x]) {
		dfsJoi2(y, v); } }

static void Precalculate(int n, int m, int ls1[], int ls2[], long long x) {
	oki.reset(); tot = -1;
	for (int i = 0; i < n; ++i) {
		lin[i].clear(); edg[i].clear(); ied[i].clear();
		psb[i] = inc[i] = fth[i] = psl[i] = szt[i] = -1; }
	for (int i = 0; i < m; ++i) {
		int x = ls1[i], y = ls2[i];
		ied[x].push_back(y); ied[y].push_back(x); }
	dfsJoi1(0); dfsJoi2(0, x); }

void Joi(int n, int m, int ls1[], int ls2[], long long x, int t) {
	Precalculate(n, m, ls1, ls2, x); }
	/*
int Move(int x);

long long Ioi(int n, int m, int ls1[], int ls2[], int p, int v, int t) {
	Precalculate(n, m, ls1, ls2, -1); long long x = ((1LL * v) << psb[p]); int nr = 0;
	while (inc[p] == -1) {
		p = fth[p]; 
		x |= (Move(p) << psb[p]); ++nr; }
	for (int i = (psl[p] + 1) % lin[inc[p]].size(); nr != 120; i = (i + 1) % lin[inc[p]].size(), ++nr) {
		int cr = lin[inc[p]][i]; x |= ((1LL * Move(cr)) << psb[cr]); }
	return x; }

#ifdef HOME
int main(void) {
	freopen("amusement.in", "r", stdin);
	freopen("amusement.out", "w", stdout); 
	int n, m, p, t; long long x; cin >> n >> m >> x >> p >> t;
	int *ls1 = new int[m], *ls2 = new int[m];
	for (int i = 0; i < m; ++i) {
		cin >> ls1[i] >> ls2[i]; }
	Joi(n, m, ls1, ls2, x, t); _cr = p;
	cout << (Ioi(n, m, ls1, ls2, p, mess[p], t) == x ? "Yes\n" : "No\n");
	assert(mst.size() == n);
	return 0; }
#endif
*/
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 10000;

static int szt[MAXN], psb[MAXN], psl[MAXN], inc[MAXN], fth[MAXN];

static bitset<MAXN> oki;
static vector<int> ied[MAXN], edg[MAXN], lin[MAXN];
/*
#ifdef HOME
int mess[MAXN], _tot, _cr;
set<int> mst;

void MessageBoard(int x, int v) {
	assert(mst.find(x) == mst.end());
	mess[x] = v; mst.insert(x); }

int Move(int x) {
	assert(_cr == fth[x] or find(edg[x].begin(), edg[x].end(), _cr) != edg[x].end()); 
	_cr = x; ++_tot; assert(_tot <= 120);
	return mess[x]; }
#endif

void MessageBoard(int x, int v);
*/
static void dfsJoi1(int x) {
	oki[x] = true; szt[x] = 1;
	sort(ied[x].begin(), ied[x].end());
	for (int y : ied[x]) { if (!oki[y]) { 
		fth[y] = x; dfsJoi1(y); 
		edg[x].push_back(y); szt[x] += szt[y]; } } }

static void dfsJoi3(int x, int c) {
	psl[x] = lin[c].size(); lin[c].push_back(x);
	for (int y : edg[x]) {
		if (inc[y] == c) {
			dfsJoi3(y, c); lin[c].push_back(x); } } }

static int tot;
static void dfsJoi2(int x, long long v) {
	if (szt[x] >= 60 and inc[x] == -1) {	
		vector<int> que(1, x); ++tot;
		for (int i = 0; i < 60; ++i) {
			int cr = que[i]; inc[cr] = tot; 
			psb[cr] = i; 
	//		if (v > 0) {
	//			MessageBoard(cr, (v >> psb[cr]) & 1); }
			for (int nx : edg[cr]) { 
				if (que.size() < 60) { 
					que.push_back(nx); } } } 
		dfsJoi3(x, tot); lin[tot].pop_back(); }
	else if (szt[x] < 60 and inc[x] == -1) {
		int nr = 0, ax = x;	
		while (inc[ax] == -1) {
			++nr; ax = fth[ax]; }
		int ps = ((119 - nr) + psl[ax]) % lin[inc[ax]].size(); 
		psb[x] = psb[lin[inc[ax]][ps]];
	//	if (v > 0) {
	//		MessageBoard(x, (v >> psb[x]) & 1); } 
	} 
	for (int y : edg[x]) {
		dfsJoi2(y, v); } }

static void Precalculate(int n, int m, int ls1[], int ls2[], long long x) {
	oki.reset(); tot = -1;
	for (int i = 0; i < n; ++i) {
		lin[i].clear(); edg[i].clear(); ied[i].clear();
		psb[i] = inc[i] = fth[i] = psl[i] = szt[i] = -1; }
	for (int i = 0; i < m; ++i) {
		int x = ls1[i], y = ls2[i];
		ied[x].push_back(y); ied[y].push_back(x); }
	dfsJoi1(0); dfsJoi2(0, x); }
/*
void Joi(int n, int m, int ls1[], int ls2[], long long x, int t) {
	Precalculate(n, m, ls1, ls2, x); }
*/	
int Move(int x);

long long Ioi(int n, int m, int ls1[], int ls2[], int p, int v, int t) {
	Precalculate(n, m, ls1, ls2, -1); long long x = ((1LL * v) << psb[p]); int nr = 0;
	while (inc[p] == -1) {
		p = fth[p]; 
		x |= (Move(p) << psb[p]); ++nr; }
	for (int i = (psl[p] + 1) % lin[inc[p]].size(); nr != 120; i = (i + 1) % lin[inc[p]].size(), ++nr) {
		int cr = lin[inc[p]][i]; x |= ((1LL * Move(cr)) << psb[cr]); }
	return x; }
/*
#ifdef HOME
int main(void) {
	freopen("amusement.in", "r", stdin);
	freopen("amusement.out", "w", stdout); 
	int n, m, p, t; long long x; cin >> n >> m >> x >> p >> t;
	int *ls1 = new int[m], *ls2 = new int[m];
	for (int i = 0; i < m; ++i) {
		cin >> ls1[i] >> ls2[i]; }
	Joi(n, m, ls1, ls2, x, t); _cr = p;
	cout << (Ioi(n, m, ls1, ls2, p, mess[p], t) == x ? "Yes\n" : "No\n");
	assert(mst.size() == n);
	return 0; }
#endif
*/

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2160 KB Output is correct
2 Correct 4 ms 2160 KB Output is correct
3 Incorrect 5 ms 2164 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 6536 KB Output is correct
2 Correct 31 ms 6384 KB Output is correct
3 Incorrect 32 ms 6424 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2396 KB Output is correct
3 Incorrect 4 ms 2184 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 6584 KB Output is correct
2 Correct 32 ms 6900 KB Output is correct
3 Correct 33 ms 6812 KB Output is correct
4 Correct 19 ms 4648 KB Output is correct
5 Incorrect 22 ms 6364 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 6640 KB Output is correct
2 Correct 33 ms 6936 KB Output is correct
3 Correct 32 ms 6920 KB Output is correct
4 Correct 19 ms 4628 KB Output is correct
5 Incorrect 23 ms 6668 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -