oj.uz

Submission #122759

# Submission time Handle Problem Language Result Execution time Memory
122759 2019-06-29T08:53:05 Z 이온조(#2999) Amusement Park (JOI17_amusement_park) C++14
0 / 100
 34 ms 3656 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> Iadj[10009];
int Iid[10009];
bool Ivs[10009];

void dfs2(int x, int d) {
	if(d == 60) return;
	Ivs[x] = 1;
	Iid[x] = d;
	for(auto& it: Iadj[x]) if(!Ivs[it]) dfs2(it, d+1);
}

void num2(int N) {
	for(int i=0; i<N; i++) if(!Ivs[i]) dfs2(i, 0);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	for(int i=0; i<M; i++) {
		int u = A[i], v = B[i];
		Iadj[u].push_back(v);
		Iadj[v].push_back(u);
	}
	for(int i=0; i<60; i++) {
		Iid[i] = i; Ivs[i] = 1;
		MessageBoard(i, !!(X & (1 << Iid[i])));
	}
	num2(N);
	for(int i=60; i<N; i++) MessageBoard(i, !!(X & (1 << Iid[i])));
	// printf("X: %lld\n", X);
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> Jadj[10009];
int Jid[10009];
bool Jvs[10009];

void dfs1(int x, int d) {
	if(d == 60) return;
	Jvs[x] = 1;
	Jid[x] = d;
	for(auto& it: Jadj[x]) if(!Jvs[it]) dfs1(it, d+1);
}

void num1(int N) {
	for(int i=0; i<N; i++) if(!Jvs[i]) dfs1(i, 0);
}

long long ret = 0;

int cl(int now, int idx, int N) {
	int x = -1;
	{
		vector<bool> vis(N, 0);
		queue<int> que; que.push(now);
		vis[now] = 1;
		while(que.size()) {
			int n = que.front(); que.pop();
			if(Jid[n] == idx) {x = n; break;}
			for(auto& it: Jadj[n]) if(!vis[it]) {
				vis[it] = 1;
				que.push(it);
			}
		}
		assert(x != -1);
	}
	{
		vector<bool> vis(N, 0);
		queue<int> que; que.push(x);
		vis[x] = 1;
		while(que.size()) {
			int n = que.front(); que.pop();
			for(auto& it: Jadj[n]) if(!vis[it]) {
				if(it == now) return n;
				vis[it] = 1;
				que.push(it);
			}
		}
	}
	assert(0);
}

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];
		Jadj[u].push_back(v);
		Jadj[v].push_back(u);
	}
	for(int i=0; i<60; i++) {
		Jid[i] = i; Jvs[i] = 1;
	}
	num1(N);
	int now = P, pr = V;
	for(int i=0; i<60; i++) {
		while(Jid[now] != i) {
			int tmp = cl(now, i, N);
			pr = Move(tmp);
			now = tmp;
		}
		ret |= (pr << i);
	}
	// printf("ret: %lld\n", ret);
	return ret;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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