답안 #41823 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41823	2018-02-21T09:48:49 Z	fest	Amusement Park (JOI17_amusement_park)	C++14	78 / 100	50 ms	14576 KB

#include "Joi.h"
// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

static const int N = 200500, inf = 1e9 * 2, MOD = (int)1e9 + 7;

static char CH[N];

static const ll INF = 1e18;

static const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
static const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};

static int in[N], timer, bit[N], out[N], up[N], a[N];

static bool was[N];

static vector<int> g[N];

static void dfs(int v) {
	was[v] = 1;
	in[v] = ++timer;
	a[in[v]] = v;
	for (auto u : g[v]) {
		if (was[u]) continue;
		dfs(u);
		up[u] = v;      
	}
	out[v] = timer;
}

void Joi(int n, int m, int A[], int B[], long long x, int T) {
	for (int i = 0; i < m; i++) {
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	} 
	dfs(0);
	for (int l = 1; l <= n;) {
		int r = out[a[l]];
		if (r - l + 1 >= 60) {
			r = l + 59;
			for (int i = l; i <= r; i++) bit[a[i]] = i - l;
		}
		else {
			int b = bit[up[a[l]]];
			if (b > r - l + 1) {
				int sz = r - l + 1;
				for (int i = l, is = 60 - sz; i <= r; i++, is++) bit[a[i]] = is;
			}
			else {
				int i = l;
				int put = 0;
				while (put < b) bit[a[i++]] = put++;
				put = 60 - ((r - l + 1) - b);
				while (put < 60) bit[a[i++]] = put++;
			}
		} 	
		l = r + 1;		
	} 
	for (int i = 0; i < n; i++) {
		if ((1ll << bit[i]) & x) MessageBoard(i, 1);
		else MessageBoard(i, 0);
	}
}

#include "Ioi.h"
// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

static const int N = 200500, inf = 1e9 * 2, MOD = (int)1e9 + 7;

static char CH[N];

static const ll INF = 1e18;

static const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
static const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};

static int ok[N], a[N], in[N], timer, up[N], out[N], ans[N], bit[N], dont;

static bool was[N];

static vector<int> g[N];                             

static void dfs(int v) {
	was[v] = 1;
	in[v] = ++timer;
	a[in[v]] = v;
	for (auto u : g[v]) {
		if (was[u]) continue;
		dfs(u);
		up[u] = v;      
	}
	out[v] = timer;
}

static void dfs1(int v, bool met) {
	if (!dont) return;
	was[v] = 1;
	for (auto u : g[v]) {
		if (was[u]) continue;
		if (met && ok[v] != ok[u]) continue; 
		if (in[u] > in[v]) {
			if (ans[bit[u]] == -1) dont--;
			ans[bit[u]] = Move(u);
			dfs1(u, met);
			if (!dont) return;
			Move(v);
		}
	}
	assert(v > 0);
	if (was[up[v]]) return;
	if (ans[bit[up[v]]] == -1) dont--;
	ans[bit[up[v]]] = Move(up[v]);
	if (!dont) return;	
	dfs1(up[v], (met | (ok[up[v]] > 0)));
}

long long Ioi(int n, int m, int A[], int B[], int start, int msg, int T) {
	for (int i = 0; i < m; i++) g[A[i]].pb(B[i]), g[B[i]].pb(A[i]);
	dfs(0);
	int ctc = 1;
	for (int l = 1; l <= n;) {
		int r = out[a[l]];
		if (r - l + 1 >= 60) {
			r = l + 59;
			for (int i = l; i <= r; i++) ok[a[i]] = ctc, bit[a[i]] = i - l;
			ctc++;
		}
		else {
			int b = bit[up[a[l]]];
			if (b > r - l + 1) {
				int sz = r - l + 1;
				for (int i = l, is = 60 - sz; i <= r; i++, is++) bit[a[i]] = is;
			}
			else {
				int i = l;
				int put = 0;
				while (put < b) bit[a[i++]] = put++;
				put = 60 - ((r - l + 1) - b);
				while (put < 60) bit[a[i++]] = put++;
			}
		} 	
		l = r + 1;		
	}
	for (int i = 0; i < 60; i++) ans[i] = -1;
	dont = 60;
	ans[bit[start]] = msg;
	dont--;
	memset(was, 0, sizeof(was));
	dfs1(start, ok[start]);
	ll ret = 0;
	for (int i = 0; i < 60; i++) ret |= ((ans[i] * 1ll) << i);
	return ret;
}

Compilation message

Joi.cpp:25:13: warning: 'CH' defined but not used [-Wunused-variable]
 static char CH[N];
             ^

Ioi.cpp:25:13: warning: 'CH' defined but not used [-Wunused-variable]
 static char CH[N];
             ^

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	10332 KB	Output is correct
2	Correct	11 ms	10864 KB	Output is correct
3	Correct	10 ms	11048 KB	Output is correct
4	Correct	10 ms	11064 KB	Output is correct
5	Correct	10 ms	11064 KB	Output is correct
6	Correct	10 ms	11132 KB	Output is correct
7	Correct	13 ms	11200 KB	Output is correct
8	Correct	11 ms	11200 KB	Output is correct
9	Correct	10 ms	11200 KB	Output is correct
10	Correct	10 ms	11200 KB	Output is correct
11	Correct	14 ms	11312 KB	Output is correct
12	Correct	10 ms	11424 KB	Output is correct
13	Correct	13 ms	11424 KB	Output is correct
14	Correct	11 ms	11424 KB	Output is correct
15	Correct	10 ms	11424 KB	Output is correct
16	Correct	13 ms	11424 KB	Output is correct
17	Correct	10 ms	11424 KB	Output is correct
18	Correct	11 ms	11424 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	14104 KB	Output is correct
2	Correct	50 ms	14320 KB	Output is correct
3	Correct	37 ms	14320 KB	Output is correct
4	Correct	34 ms	14320 KB	Output is correct
5	Correct	33 ms	14320 KB	Output is correct
6	Correct	27 ms	14320 KB	Output is correct
7	Correct	28 ms	14320 KB	Output is correct
8	Correct	31 ms	14320 KB	Output is correct
9	Correct	28 ms	14320 KB	Output is correct
10	Correct	24 ms	14320 KB	Output is correct
11	Correct	25 ms	14320 KB	Output is correct
12	Correct	23 ms	14320 KB	Output is correct
13	Correct	32 ms	14320 KB	Output is correct
14	Correct	26 ms	14320 KB	Output is correct
15	Correct	25 ms	14320 KB	Output is correct
16	Correct	28 ms	14320 KB	Output is correct
17	Correct	26 ms	14320 KB	Output is correct
18	Correct	35 ms	14320 KB	Output is correct
19	Correct	26 ms	14320 KB	Output is correct
20	Correct	28 ms	14320 KB	Output is correct
21	Correct	22 ms	14320 KB	Output is correct
22	Correct	25 ms	14320 KB	Output is correct
23	Correct	28 ms	14320 KB	Output is correct
24	Correct	27 ms	14320 KB	Output is correct
25	Correct	28 ms	14320 KB	Output is correct
26	Correct	30 ms	14320 KB	Output is correct
27	Correct	25 ms	14320 KB	Output is correct
28	Correct	26 ms	14320 KB	Output is correct
29	Correct	30 ms	14320 KB	Output is correct
30	Correct	27 ms	14320 KB	Output is correct
31	Correct	11 ms	14320 KB	Output is correct
32	Correct	10 ms	14320 KB	Output is correct
33	Correct	13 ms	14320 KB	Output is correct
34	Correct	12 ms	14320 KB	Output is correct
35	Correct	11 ms	14320 KB	Output is correct
36	Correct	11 ms	14320 KB	Output is correct
37	Correct	11 ms	14320 KB	Output is correct
38	Correct	11 ms	14320 KB	Output is correct
39	Correct	10 ms	14320 KB	Output is correct
40	Correct	12 ms	14320 KB	Output is correct
41	Correct	11 ms	14320 KB	Output is correct
42	Correct	14 ms	14320 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	14320 KB	Output is correct
2	Correct	10 ms	14320 KB	Output is correct
3	Correct	10 ms	14320 KB	Output is correct
4	Correct	12 ms	14320 KB	Output is correct
5	Correct	14 ms	14320 KB	Output is correct
6	Correct	14 ms	14320 KB	Output is correct
7	Correct	12 ms	14320 KB	Output is correct
8	Correct	12 ms	14320 KB	Output is correct
9	Correct	23 ms	14320 KB	Output is correct
10	Correct	26 ms	14320 KB	Output is correct
11	Correct	26 ms	14320 KB	Output is correct
12	Correct	10 ms	14320 KB	Output is correct
13	Correct	12 ms	14320 KB	Output is correct
14	Correct	12 ms	14320 KB	Output is correct
15	Correct	12 ms	14320 KB	Output is correct

Subtask #4
50.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	14320 KB	Output is correct
2	Partially correct	41 ms	14320 KB	Partially correct
3	Correct	39 ms	14448 KB	Output is correct
4	Correct	26 ms	14576 KB	Output is correct
5	Correct	33 ms	14576 KB	Output is correct
6	Correct	27 ms	14576 KB	Output is correct
7	Correct	27 ms	14576 KB	Output is correct
8	Correct	31 ms	14576 KB	Output is correct
9	Correct	30 ms	14576 KB	Output is correct
10	Correct	26 ms	14576 KB	Output is correct
11	Correct	27 ms	14576 KB	Output is correct
12	Correct	24 ms	14576 KB	Output is correct
13	Correct	24 ms	14576 KB	Output is correct
14	Correct	33 ms	14576 KB	Output is correct
15	Correct	33 ms	14576 KB	Output is correct
16	Correct	26 ms	14576 KB	Output is correct
17	Correct	25 ms	14576 KB	Output is correct
18	Correct	25 ms	14576 KB	Output is correct
19	Partially correct	25 ms	14576 KB	Partially correct
20	Correct	20 ms	14576 KB	Output is correct
21	Correct	24 ms	14576 KB	Output is correct
22	Correct	25 ms	14576 KB	Output is correct
23	Correct	33 ms	14576 KB	Output is correct
24	Correct	27 ms	14576 KB	Output is correct
25	Correct	30 ms	14576 KB	Output is correct
26	Correct	26 ms	14576 KB	Output is correct
27	Correct	28 ms	14576 KB	Output is correct
28	Correct	27 ms	14576 KB	Output is correct
29	Correct	28 ms	14576 KB	Output is correct
30	Correct	25 ms	14576 KB	Output is correct

Subtask #5
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	14576 KB	Output is correct
2	Correct	39 ms	14576 KB	Output is correct
3	Correct	39 ms	14576 KB	Output is correct
4	Correct	26 ms	14576 KB	Output is correct
5	Correct	27 ms	14576 KB	Output is correct
6	Correct	28 ms	14576 KB	Output is correct
7	Correct	35 ms	14576 KB	Output is correct
8	Correct	27 ms	14576 KB	Output is correct
9	Correct	28 ms	14576 KB	Output is correct
10	Correct	33 ms	14576 KB	Output is correct
11	Correct	33 ms	14576 KB	Output is correct
12	Correct	26 ms	14576 KB	Output is correct
13	Correct	25 ms	14576 KB	Output is correct
14	Correct	30 ms	14576 KB	Output is correct
15	Incorrect	26 ms	14576 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

답안 #41823

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 50.0 / 55.0

Subtask #5 0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
50.0 / 55.0

Subtask #5
0 / 17.0