oj.uz

Submission #49430

# Submission time Handle Problem Language Result Execution time Memory
49430 2018-05-28T18:30:01 Z WLZ Amusement Park (JOI17_amusement_park) C++17
10 / 100
 104 ms 4328 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

class DSU {
	private: vector<int> p, rank;
	public:
		DSU(int n) {p.assign(n, -1); rank.assign(n, 0); }
		int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }
		bool sameSet(int x, int y) { return root(x) == root(y); }
		void connect(int x, int y) { x = root(x), y = root(y); if (rank[x] > rank[y]) p[y] = x; else { p[x] = y; if (rank[x] == rank[y]) rank[y]++; }}
};

vector<vector<int>> joiG;
vector<int> joiInd;
int joiCnt;
vector<int> joiV;
bitset<60> joiUsedInd;

void joiDfs(int u, int par) {
	//joiCnt++;
	if (joiCnt >= 60) return;
	joiCnt++;
	if (joiInd[u] != -1) joiUsedInd[joiInd[u]] = true;
	joiV.push_back(u);
	for (int& v : joiG[u]) {
		if (v != par) {
			joiDfs(v, u);
		}
	}
	return;
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	DSU dsu(N);
	joiG.resize(N);
	joiInd.assign(N, -1);
	for (int i = 0; i < M; i++) {
		if (!dsu.sameSet(A[i], B[i])) {
			dsu.connect(A[i], B[i]);
			joiG[A[i]].push_back(B[i]);
			joiG[B[i]].push_back(A[i]);
		}
	}
	for (int i = 0; i < N; i++) {
		joiV.clear();
#ifdef DEBUG
		//printf("%d\n", i);
#endif
		joiCnt = 0;
		joiUsedInd.reset();
		joiDfs(i, -1);
		//for (int& tmp : joiV) 
		int cnt = 0;
		for (int& v : joiV) {
			while (joiUsedInd[cnt]) cnt++;
			if (joiInd[v] != -1) continue;
			joiInd[v] = cnt++;
		}
	}
#ifdef DEBUG
	for (int i = 0; i < N; i++) {
		//printf("%d %d\n", i, joiInd[i]);	
	}
#endif
	vector<int> bin;
	for (int i = 0; i < 60; i++) {
		if (X & (1ll << i)) bin.push_back(1);
		else bin.push_back(0);
	}
	for (int i = 0; i < N; i++) {
		MessageBoard(i, bin[joiInd[i]]);
	}
	return;
}

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

class DSU {
	private: vector<int> p, rank;
	public:
		DSU(int n) { p.assign(n, -1); rank.assign(n, 0); }
		int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]);  }
		bool sameSet(int x, int y) { return root(x) == root(y); }
		void connect(int x, int y) { x = root(x), y = root(y); if (rank[x] > rank[y]) p[y] = x; else { p[x] = y; if (rank[x] == rank[y]) rank[y]++; } }
};

vector<vector<int>> ioiG;
int ioiCnt;
bitset<60> ioiUsedInd;
vector<int> ioiInd;
vector<int> ioiV;
vector<int> v(60, -1);
bitset<10005> setV;
int cur, dfsCur;
int _P;

void ioiDfs(int u, int par) {
	//ioiCnt++;
	if (ioiCnt >= 60) return;
	ioiCnt++;
	if (ioiInd[u] != -1) ioiUsedInd[ioiInd[u]] = true;
	ioiV.push_back(u);
	if (cur == _P) setV[u] = true;
	for (int& v : ioiG[u]) {
		if (v != par) {
			ioiDfs(v, u);
		}
	}
	return;
}

void dfs(int u, int par) {
#ifdef DEBUG
	//printf("%d %d\n", u, par);
#endif	
	for (int& neigh : ioiG[u]) {
		if (neigh != par && setV[neigh]) {
			int tmp = Move(neigh);
#ifdef DEBUG
			//printf("%d\n", tmp);
#endif
			v[ioiInd[neigh]] = tmp;
			cur = neigh;
			dfs(neigh, u);
			if (cur != u) {
				Move(u);
				cur = u;
			}
		}
	}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	_P = P;
	DSU dsu(N);
	ioiG.resize(N);
	ioiInd.assign(N, -1);
	for (int i = 0; i < M; i++) {
		if (!dsu.sameSet(A[i], B[i])) {
			dsu.connect(A[i], B[i]);
			ioiG[A[i]].push_back(B[i]);
			ioiG[B[i]].push_back(A[i]);
		}
	}
	for (int i = 0; i < N; i++) {
		ioiV.clear();
		ioiCnt = 0;
		ioiUsedInd.reset();
		cur = i;
		ioiDfs(i, -1);
		int cnt = 0;
		for (int& v : ioiV) {
#ifdef DEBUG
			//printf("%d\n", v);
#endif
			while (ioiUsedInd[cnt]) cnt++;
			if (ioiInd[v] != -1) continue;
			ioiInd[v] = cnt++;
#ifdef DEBUG
			//printf("%d\n", cnt);
#endif
		}
	}
#ifdef DEBUG
	//for (int i = 0; i < N; i++) printf("%d %d\n", i, ioiInd[i]);
#endif
	v[ioiInd[P]] = V;
	dfs(P, -1);
#ifdef DEBUG
	//for (int& bit : v) printf("%d ", bit);
#endif
	//putchar('\n');
	long long ans = 0ll;
	for (int i = 0; i < 60; i++) {
		if (v[i] == 1) ans += (1ll << i);
	}
	return ans;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4008 KB Output is correct
2 Correct 4 ms 4008 KB Output is correct
3 Correct 4 ms 4008 KB Output is correct
4 Correct 8 ms 4008 KB Output is correct
5 Correct 8 ms 4008 KB Output is correct
6 Correct 8 ms 4008 KB Output is correct
7 Correct 9 ms 4008 KB Output is correct
8 Correct 8 ms 4008 KB Output is correct
9 Correct 46 ms 4008 KB Output is correct
10 Correct 32 ms 4008 KB Output is correct
11 Correct 32 ms 4008 KB Output is correct
12 Correct 5 ms 4008 KB Output is correct
13 Correct 5 ms 4008 KB Output is correct
14 Correct 5 ms 4008 KB Output is correct
15 Correct 5 ms 4008 KB Output is correct

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 4328 KB Output is correct
2 Incorrect 90 ms 4328 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -