제출 #49368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49368		WLZ	Amusement Park (JOI17_amusement_park)	C++17	10 / 100	51 ms	7216 KiB

Joi

#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;
}

Ioi

#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
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17