oj.uz

Submission #49368

# Submission time Handle Problem Language Result Execution time Memory
49368 2018-05-27T16:49:20 Z WLZ Amusement Park (JOI17_amusement_park) C++17
10 / 100
 51 ms 7216 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;

class DSU {
	private: vector<int> p, rank;
	public: 
		DSU(int n) {
			p.assign(n, -1);
			for (int i = 0; i < n; i++) p[i] = i;
			rank.assign(n, 0);
		}
		int root(int x) {
			return p[x] == x ? 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 (x != y) {
				if (rank[x] > rank[y]) p[y] = x;
				else {
					p[x] = y;
					if (rank[x] == rank[y]) rank[y]++;
				}
			}
			return;
		}
};

vector<int> ind, bin;
vector<vector<int>> g;
int cnt = 0;

void preorder(int u, int par) {
	ind[u] = cnt++;
	MessageBoard(u, bin[ind[u] % 60]);
	for (int& v : g[u]) {
		if (v != par) {
			preorder(v, u);
		}
	}
	return;
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	DSU dsu(N);
	ind.resize(N);
	g.resize(N);
	for (int i = 0; i < 60; i++) {
		if (X & (1ll << i)) bin.push_back(1);
		else bin.push_back(0);
	}
	//reverse(bin.begin(), bin.end());
	//for (int x : bin) printf("%d ", x);
	for (int i = 0; i < M; i++) {
		if (!dsu.sameSet(A[i], B[i])) {
			dsu.connect(A[i], B[i]);
			g[A[i]].push_back(B[i]);
			g[B[i]].push_back(A[i]);
		}
	}
	preorder(0, -1);
	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);
			for (int i = 0; i < n; i++) p[i] = i;
			rank.assign(n, 0);
		}
		int root(int x) {
			return p[x] == x ? 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 (x != y) {
				if (rank[x] > rank[y]) p[y] = x;
				else {
					p[x] = y;
					if (rank[x] == rank[y]) rank[y]++;
				}
			}
		}
};

vector<int> ind2;
vector<vector<int>> g2;
vector<int> p;
vector<int> bin2(60, -1);
vector<set<int>> adj;
int needed = 60;
int cnt2 = 0;
int cur;

void preorder2(int u, int par) {
	ind2[u] = cnt2++;
	for (int& v : g2[u]) {
		if (v != par) {
			preorder2(v, u);
		}
	}
}

void dfs(int u) {
	//printf("%d %d\n", u, cur);
	if (needed <= 0) return;
	for (int& v : g2[u]) {
		if (v != p[u]) {
			if (bin2[ind2[v] % 60] == -1) {
				//printf("yep\n");
				p[v] = u;
				int tmp = Move(v);
				//printf("%d ", tmp);
				bin2[ind2[v] % 60] = tmp;
				//if (tmp == 1) printf("%d\n", ind2[v] % 60);
				needed--;
				cur = v;
				dfs(v);
				//printf("%d\n", cur);
				if (cur != u && needed && adj[cur].count(u)) Move(u), cur = u;
				//printf("yep %d\n", cur);
			}
			if (needed <= 0) return;
		}
	}
	if (cur != u) /*printf("%d %d\n", cur, u),*/ Move(u), cur = u;
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	ind2.resize(N);
	DSU dsu(N);
	g2.resize(N);
	p.resize(N);
	adj.resize(N);
	cur = P;
	for (int i = 0; i < M; i++) {
		if (!dsu.sameSet(A[i], B[i])) {
			dsu.connect(A[i], B[i]);
			g2[A[i]].push_back(B[i]);
			adj[A[i]].insert(B[i]);
			g2[B[i]].push_back(A[i]);
			adj[B[i]].insert(A[i]);
		}
	}
	preorder2(0, -1);
	//for (int i = 0; i < N; i++) printf("%d %d\n", i, ind2[i]);
	bin2[ind2[P] % 60] = V;
	//for (int& x : bin2) printf("%d ", x);
	long long ans = 0ll;
	dfs(P);
	//for (int& x : bin2) printf("%d ", x);
	for (int i = 0; i < 60; i++) {
		//printf("%d ", bin2[i]);
		//assert(bin2[i] != -1);
		if (bin2[i]) ans += (1ll << i);
		//printf("%lld\n", ans);
	}
  	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 608 KB Output is correct
2 Correct 6 ms 872 KB Output is correct
3 Incorrect 6 ms 1064 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5300 KB Output is correct
2 Incorrect 48 ms 6812 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6888 KB Output is correct
2 Correct 4 ms 6888 KB Output is correct
3 Correct 5 ms 6888 KB Output is correct
4 Correct 8 ms 6888 KB Output is correct
5 Correct 6 ms 6888 KB Output is correct
6 Correct 8 ms 6888 KB Output is correct
7 Correct 7 ms 6888 KB Output is correct
8 Correct 7 ms 6888 KB Output is correct
9 Correct 20 ms 7028 KB Output is correct
10 Correct 20 ms 7168 KB Output is correct
11 Correct 20 ms 7192 KB Output is correct
12 Correct 6 ms 7216 KB Output is correct
13 Correct 5 ms 7216 KB Output is correct
14 Correct 5 ms 7216 KB Output is correct
15 Correct 5 ms 7216 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7216 KB Output is correct
2 Correct 39 ms 7216 KB Output is correct
3 Correct 37 ms 7216 KB Output is correct
4 Correct 34 ms 7216 KB Output is correct
5 Correct 28 ms 7216 KB Output is correct
6 Correct 28 ms 7216 KB Output is correct
7 Correct 30 ms 7216 KB Output is correct
8 Correct 36 ms 7216 KB Output is correct
9 Incorrect 27 ms 7216 KB Wrong Answer [7]
10 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7216 KB Output is correct
2 Correct 39 ms 7216 KB Output is correct
3 Correct 39 ms 7216 KB Output is correct
4 Correct 30 ms 7216 KB Output is correct
5 Incorrect 27 ms 7216 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -