oj.uz

Submission #35992

# Submission time Handle Problem Language Result Execution time Memory
35992 2017-12-04T06:08:34 Z cheater2k Amusement Park (JOI17_amusement_park) C++14
10 / 100
 35 ms 7372 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 10005;

namespace JOI {
	int n, m;
	int pos[MAX];
	int par[MAX];
	int id[MAX];
	int ncomp;
	vector<int> comp[MAX];
	vector<int> G[MAX];
	long long X;
	
	void build() {
		vector< pair<int,int> > edges;
		for (int i = 0; i < n; ++i) pos[i] = 0;
		queue <int> q; q.push(0); pos[0] = 1;
		while(!q.empty()) {
			int u = q.front(); q.pop();
			for (int v : G[u]) {
				if (!pos[v]) q.push(v), pos[v] = 1, edges.push_back(make_pair(u,v));
			}
		}
		for (int i = 0; i < n; ++i) G[i].clear(), pos[i] = 0;
		for (auto e : edges) G[e.first].push_back(e.second), G[e.second].push_back(e.first);
	}

	void dfs(int u) {
		pos[u] = ncomp; comp[ncomp].push_back(u);
		if (comp[ncomp].size() == 60) ++ncomp;
		for (int v : G[u]) if (!pos[v]) {
			par[v] = u;
			dfs(v);
		}
	}

	void add(int u, int c) {
		if (comp[c].size() == 60) return;
		comp[c].push_back(u);
		for (int v : G[u]) {
			if (pos[v] == pos[u]) add(v, c);
		}
	}

	void prepare() {
		build();
		dfs(0);
		for (int i = 1; i <= ncomp; ++i) if (comp[i].size() == 60) {
			for (int j = 0; j < comp[i].size(); ++j) id[comp[i][j]] = j;
		}

		if (comp[ncomp].empty()) --ncomp;
		for (int i = 1; i <= ncomp; ++i) {
			if (comp[i].size() < 60) {
				int sz = comp[i].size();
				int root = comp[i][0];
				root = par[root];
				add(root, i);

				long long mask = 0;
				vector<int> rem;
				for (int j = sz; j < 60; ++j) mask |= (1LL << id[comp[i][j]]);
				for (int j = 0; j < 60; ++j) if (!(mask >> j & 1)) rem.push_back(j);
				for (int j = 0; j < sz; ++j) id[comp[i][j]] = rem.back(), rem.pop_back();
			}
		}
	}

	void assign() {
		JOI::prepare();
		for (int i = 0; i < n; ++i) MessageBoard(i, (X >> id[i] & 1));
	}
};

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  JOI::n = N; 
  JOI::m = M;
  JOI::X = X;
  for (int i = 0; i < M; ++i) JOI::G[A[i]].push_back(B[i]), JOI::G[B[i]].push_back(A[i]);
  JOI::assign();
}

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

const int MAX = 10005;

namespace IOI {
	int n, m;
	int pos[MAX];
	int par[MAX];
	int id[MAX];
	int ncomp;
	vector<int> comp[MAX];
	vector<int> G[MAX];
	long long X;
	
	void build() {
		vector< pair<int,int> > edges;
		for (int i = 0; i < n; ++i) pos[i] = 0;
		queue <int> q; q.push(0); pos[0] = 1;
	
		while(!q.empty()) {
			int u = q.front(); q.pop();
			for (int v : G[u]) {
				if (!pos[v]) q.push(v), pos[v] = 1, edges.push_back(make_pair(u,v));
			}
		}
		for (int i = 0; i < n; ++i) G[i].clear(), pos[i] = 0;
		for (auto e : edges) G[e.first].push_back(e.second), G[e.second].push_back(e.first);
	}

	void dfs(int u) {
		pos[u] = ncomp; 
		comp[ncomp].push_back(u);
		if (comp[ncomp].size() == 60) ++ncomp;
		for (int v : G[u]) if (!pos[v]) {
			par[v] = u;
			dfs(v);
		}
	}

	void add(int u, int c) {
		if (comp[c].size() == 60) return;
		comp[c].push_back(u);
		for (int v : G[u]) {
			if (pos[v] == pos[u]) add(v, c);
		}
	}

	void prepare() {
		build();
		ncomp = 1;
		dfs(0);
		
		for (int i = 1; i <= ncomp; ++i) if (comp[i].size() == 60) {
			for (int j = 0; j < comp[i].size(); ++j) id[comp[i][j]] = j;
		}
		if (comp[ncomp].empty()) --ncomp;
		
		for (int i = 1; i <= ncomp; ++i) {
			if (comp[i].size() < 60) {
				int sz = comp[i].size();
				int root = comp[i][0];
				root = par[root];
				add(root, i);

				long long mask = 0;
				vector<int> rem;
				for (int j = sz; j < 60; ++j) mask |= (1LL << id[comp[i][j]]);
				for (int j = 0; j < 60; ++j) if (!(mask >> j & 1)) rem.push_back(j);
				for (int j = 0; j < sz; ++j) id[comp[i][j]] = rem.back(), rem.pop_back();
			}
		}
	}

	void Ask(int u, int p, int c) {
		pos[u] = 1;
		for (int v : G[u]) if (find(comp[c].begin(), comp[c].end(), v) != comp[c].end()) {
			if (pos[v] == 0) {
				int k = Move(v); X |= ((1LL << id[v]) * k);
				Ask(v, u, c);
			}
		}
		if (p != -1) Move(p);
	}

	void solve(int P, int V) {
		prepare();
		int c = pos[P];
		X |= ((1LL << id[P]) * V);
		for (int i = 0; i < n; ++i) pos[i] = 0;
		Ask(P, -1, c);
	}
};

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  IOI::n = N; 
  IOI::m = M;
  for (int i = 0; i < M; ++i) IOI::G[A[i]].push_back(B[i]), IOI::G[B[i]].push_back(A[i]);
  IOI::solve(P, V);
	return IOI::X;
}

Compilation message

Joi.cpp: In function 'void JOI::prepare()':
Joi.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < comp[i].size(); ++j) id[comp[i][j]] = j;
                      ^

Ioi.cpp: In function 'void IOI::prepare()':
Ioi.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < comp[i].size(); ++j) id[comp[i][j]] = j;
                      ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5924 KB Output is correct
2 Correct 0 ms 5924 KB Output is correct
3 Correct 0 ms 5924 KB Output is correct
4 Correct 0 ms 6188 KB Output is correct
5 Correct 0 ms 6188 KB Output is correct
6 Correct 0 ms 6188 KB Output is correct
7 Correct 0 ms 6188 KB Output is correct
8 Correct 0 ms 6188 KB Output is correct
9 Correct 12 ms 7364 KB Output is correct
10 Correct 12 ms 7372 KB Output is correct
11 Correct 15 ms 7372 KB Output is correct
12 Correct 0 ms 5924 KB Output is correct
13 Correct 0 ms 5924 KB Output is correct
14 Correct 0 ms 5924 KB Output is correct
15 Correct 0 ms 5924 KB Output is correct

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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