oj.uz

Submission #684035

# Submission time Handle Problem Language Result Execution time Memory
684035 2023-01-20T05:17:18 Z flappybird Amusement Park (JOI17_amusement_park) C++14
0 / 100
 3000 ms 262144 KB 
#include "Joi.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define MAX 10101
#define LEN 60
namespace JOI {
	vector<int> adj[MAX];
	vector<int> tree[MAX];
	queue<int> q;
	int cnt = 0;
	int col[MAX];
	int ans[MAX];
	int num[MAX];
	int vis[MAX];
	int prt[MAX];
	void dfs(int x, int p, int c) {
		col[x] = c;
		ans[x] = ++cnt;
		for (auto v : tree[x]) if (p != v) {
			if (cnt < LEN) dfs(v, x, c);
			else q.push(v);
		}
	}
	void getnum(int x, int p = -1) {
		if (~p) tree[p].push_back(x), tree[x].push_back(p), prt[x] = p;
		num[x] = 1;
		vis[x] = 1;
		for (auto v : adj[x]) if (!vis[v]) {
			getnum(v, x);
			num[x] += num[v];
		}
	}
	vector<int> lst;
	void make_lst(int x, int p, int c) {
		for (auto v : tree[x]) if (v != p && col[v] == c) make_lst(v, x, c);
		lst.push_back(x);
	}
	void color_rem(int x, int p, int c) {
		ans[x] = ans[lst.back()];
		lst.pop_back();
		col[x] = c;
		for (auto v : tree[x]) if (v != p) color_rem(v, x, c);
	}
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	int i;
	for (i = 0; i < M; i++) JOI::adj[A[i]].push_back(B[i]), JOI::adj[B[i]].push_back(A[i]);
	JOI::getnum(0);
	JOI::q.push(0);
	int cols = 0;
	vector<int> rem;
	while (JOI::q.size()) {
		int t = JOI::q.front();
		JOI::q.pop();
		if (JOI::num[t] < LEN) rem.push_back(t);
		else JOI::cnt = 0, JOI::dfs(t, -1, ++cols);
	}
	for (auto v : rem) {
		cols++;
		JOI::make_lst(JOI::prt[v], -1, JOI::col[JOI::prt[v]]);
		reverse(JOI::lst.begin(), JOI::lst.end());
		JOI::color_rem(v, JOI::prt[v], cols);
		JOI::lst.clear();
	}
	for (i = 0; i < N; i++) MessageBoard(i, (X >> (JOI::ans[i] - 1)) & 1ll);
}

#include "Ioi.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define MAX 10101
#define LEN 60
namespace IOI {
	vector<int> adj[MAX];
	vector<int> tree[MAX];
	queue<int> q;
	int cnt = 0;
	int col[MAX];
	int ans[MAX];
	int num[MAX];
	int vis[MAX];
	int prt[MAX];
	void dfs(int x, int p, int c) {
		col[x] = c;
		ans[x] = ++cnt;
		for (auto v : tree[x]) if (p != v) {
			if (cnt < LEN) dfs(v, x, c);
			else q.push(v);
		}
	}
	void getnum(int x, int p = -1) {
		if (~p) tree[p].push_back(x), tree[x].push_back(p), prt[x] = p;
		num[x] = 1;
		vis[x] = 1;
		for (auto v : adj[x]) if (!vis[v]) {
			getnum(v, x);
			num[x] += num[v];
		}
	}
	vector<int> lst;
	void make_lst(int x, int p, int c) {
		for (auto v : tree[x]) if (v != p && col[v] == c) make_lst(v, x, c);
		lst.push_back(x);
	}
	void color_rem(int x, int p, int c) {
		ans[x] = ans[lst.back()];
		lst.pop_back();
		col[x] = c;
		for (auto v : tree[x]) if (v != p) color_rem(v, x, c);
	}
	vector<int> rems[MAX];
	int chk[MAX];
	int Xs[MAX];
	void getans(int x, int p = -1) {
		for (auto v : tree[x]) if (v != p && chk[v]) {
			Xs[ans[v] - 1] = Move(v);
			getans(v, x);
			Move(x);
		}
	}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	int i;
	for (i = 0; i < M; i++) IOI::adj[A[i]].push_back(B[i]), IOI::adj[B[i]].push_back(A[i]);
	IOI::getnum(0);
	IOI::q.push(0);
	int cols = 0;
	vector<int> rem;
	while (IOI::q.size()) {
		int t = IOI::q.front();
		IOI::q.pop();
		if (IOI::num[t] < LEN) rem.push_back(t);
		else IOI::cnt = 0, IOI::dfs(t, -1, ++cols);
	}
	int x = cols;
	for (auto v : rem) {
		cols++;
		IOI::make_lst(IOI::prt[v], -1, IOI::col[IOI::prt[v]]);
		reverse(IOI::lst.begin(), IOI::lst.end());
		IOI::color_rem(v, IOI::prt[v], cols);
		swap(IOI::lst, IOI::rems[cols]);
		IOI::lst.clear();
	}
	int C = IOI::col[P];
	for (i = 0; i < N; i++) if (IOI::col[i] == C) IOI::chk[i] = 1;
	for (auto v : IOI::rems[C]) IOI::chk[v] = 1;
	IOI::Xs[IOI::ans[P] - 1] = V;
	IOI::getans(P);
	ll X = 0;
	for (i = 0; i < LEN; i++) X |= (ll)IOI::Xs[i] << (ll)i;
	return X;
}

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:71:6: warning: unused variable 'x' [-Wunused-variable]
   71 |  int x = cols;
      |      ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1792 KB Output is correct
2 Correct 2 ms 1796 KB Output is correct
3 Correct 2 ms 1864 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 2 ms 1796 KB Output is correct
6 Correct 2 ms 1932 KB Output is correct
7 Runtime error 1262 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 93396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1800 KB Output is correct
2 Correct 2 ms 1792 KB Output is correct
3 Correct 2 ms 1800 KB Output is correct
4 Execution timed out 3085 ms 18888 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 157568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3087 ms 90060 KB Time limit exceeded
2 Halted 0 ms 0 KB -