oj.uz

Submission #946999

# Submission time Handle Problem Language Result Execution time Memory
946999 2024-03-15T09:56:31 Z mansur Amusement Park (JOI17_amusement_park) C++17
10 / 100
 27 ms 6440 KB 
#include "Joi.h"
#include<bits/stdc++.h>	

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int NN = 1e4;

int d[2][NN];
vector<int> g[NN];

int get(int x, int k, int n) {
	for (int i = 0; i < n; i++) d[k][i] = -1;
	queue<int> q;
	q.push(x);
	int mx = x;
	d[k][x] = 0;
	while (sz(q)) {
		x = q.front();
		q.pop();
		for (int to: g[x]) {
			if (d[k][to] == -1) {
				d[k][to] = d[k][x] + 1;
				q.push(to);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (d[k][i] > d[k][mx]) {
			mx = i;
		}
	}
	return mx;
}

int cur, was[NN], dpt[NN];
vector<pii> s[NN];

void dfs(int u) {
    was[u] = 1;
	for (int to: g[u]) {
		if (was[to]) continue;
		dfs(to);
		dpt[u] = max(dpt[u], dpt[to] + 1);
		s[u].push_back({dpt[to], to});
	}
	sort(rall(s[u]));
}

ll x;

void mrk(int u) {
	MessageBoard(u, (x >> cur & 1));
	cur++;
	for (auto to: s[u]) mrk(to.s);		
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {	
	x = X;
	for (int i = 0; i < M; i++) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	int a = get(0, 0, N);
	int b = get(a, 1, N);
	if (d[1][b] < 59) {
		dfs(0);
		mrk(0);
		return;
	}
	for (int i = 0; i < N; i++) {
		d[1][i] %= 60;
		MessageBoard(i, (X >> d[1][i] & 1));
	}
}

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

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int Nn = 1e4;

int dd[2][Nn], nxt[Nn], prv[Nn];
vector<int> gg[Nn];

int gett(int x, int k, int n) {
	for (int i = 0; i < n; i++) dd[k][i] = -1;
	queue<int> q;
	q.push(x);
	int s = x;
	dd[k][x] = 0;
	while (sz(q)) {
		x = q.front();
		q.pop();
		for (int to: gg[x]) {
			if (dd[k][to] == -1) {
				dd[k][to] = dd[k][x] + 1;
				prv[to] = x;
				q.push(to);
			}
		}
	}
	int mx = s;
	for (int i = 0; i < n; i++) {
		if (dd[k][i] > dd[k][mx]) {
			mx = i;
		}
	}
	int v = mx;
	while (mx != s) {
		nxt[prv[mx]] = mx;
		mx = prv[mx];	
	}
	return v;
}

vector<pii> h[Nn];
int dt[Nn], wes[Nn];
ll vl[Nn], cr, cnt;
ll ans, pr[Nn];

void dffs(int u) {
    wes[u] = 1;
	for (int to: gg[u]) {
		if (wes[to]) continue;
		pr[to] = u;
		dffs(to);
		dt[u] = max(dt[u], dt[to] + 1);
		h[u].push_back({dt[to], to});
	}
	sort(rall(h[u]));
}

void mrkk(int u) {
	vl[u] = cr++;
	for (auto to: h[u]) mrkk(to.s);
	reverse(all(h[u]));	
}

int vv, used[60], mv;

void git(int u) {
	if (vl[u] < 60 && !used[vl[u]]) {
		used[vl[u]] = 1;
		ans += (1ll << vl[u]) * vv;
		cnt++;
	}
	for (auto to: h[u]) {
		if (vl[to.s] < 60 && !used[vl[to.s]]) {
			mv++;
			if (mv > 960) cout << 5 / 0;
			vv = Move(to.s);
			git(to.s);
		}
	}
	if (cnt == 60) return;
	mv++;
	if (mv > 960) cout << 5 / 0;
	vv = Move(pr[u]);
	git(pr[u]);
}

void bfs(int u, int v) {
	queue<int> q;
	vector<int> d(Nn, -1), p(Nn);
	q.push(u);
	d[u] = 0;
	while (sz(q)) {
		int x = q.front();
		q.pop();
		if (x == v) break;
		for (int to: gg[x]) {
			if (d[to] == -1) {
				d[to] = d[x] + 1;
				p[to] = x;
				q.push(to);
			}
		}
	}
	vector<int> s;
	while (v != u) {
	 	s.push_back(v);
	 	v = p[v];
	}
	reverse(all(s));
	for (int x: s) {
		vv = Move(x);
	}
}

long long Ioi(int N, int M, int A[], int B[], int p, int v, int T) {
	for (int i = 0; i < M; i++) {
		gg[A[i]].push_back(B[i]);
		gg[B[i]].push_back(A[i]);
	}
	int a = gett(0, 0, N);
	int b = gett(a, 1, N);
	if (dd[1][b] < 59) {
		dffs(0);
		mrkk(0);
		int ps = p;
		while (vl[ps] >= 60) ps = pr[ps];
		bfs(p, ps);		
		git(ps);
		return ans;		
	}
	for (int i = 1; i <= 60; i++) {
		ll b = (dd[1][p] % 60);
		if (v) ans += (1ll << b);
		bool ok = 0;
		for (int to: gg[p]) {
			if (dd[1][to] + 1 == dd[1][p]) {
				v = Move(to);
				p = to;
				ok = 1;
				break;
			}
		}  
		if (!ok) {
			ans = 0;                                                                                          			
			for (ll j = 0; j < 60; j++) {
				ans += (1ll << j) * v;
				v = Move(nxt[p]);
				p = nxt[p];
			}
			return ans;
		}
	}
	return ans;
}

Compilation message

Ioi.cpp: In function 'void git(int)':
Ioi.cpp:86:28: warning: division by zero [-Wdiv-by-zero]
   86 |    if (mv > 960) cout << 5 / 0;
      |                          ~~^~~
Ioi.cpp:93:26: warning: division by zero [-Wdiv-by-zero]
   93 |  if (mv > 960) cout << 5 / 0;
      |                        ~~^~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6168 KB Output is correct
2 Correct 19 ms 6436 KB Output is correct
3 Correct 19 ms 6284 KB Output is correct
4 Correct 13 ms 4144 KB Output is correct
5 Correct 13 ms 3632 KB Output is correct
6 Correct 11 ms 3392 KB Output is correct
7 Correct 10 ms 3384 KB Output is correct
8 Correct 11 ms 3392 KB Output is correct
9 Correct 10 ms 3392 KB Output is correct
10 Incorrect 12 ms 4168 KB Wrong Answer [7]
11 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1824 KB Output is correct
2 Correct 1 ms 1824 KB Output is correct
3 Correct 2 ms 1808 KB Output is correct
4 Correct 2 ms 1864 KB Output is correct
5 Correct 2 ms 1856 KB Output is correct
6 Correct 2 ms 1860 KB Output is correct
7 Correct 2 ms 1856 KB Output is correct
8 Correct 2 ms 1852 KB Output is correct
9 Correct 9 ms 3380 KB Output is correct
10 Correct 8 ms 3384 KB Output is correct
11 Correct 11 ms 3472 KB Output is correct
12 Correct 1 ms 1808 KB Output is correct
13 Correct 1 ms 1812 KB Output is correct
14 Correct 1 ms 1816 KB Output is correct
15 Correct 1 ms 1812 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6428 KB Output is correct
2 Correct 20 ms 6176 KB Output is correct
3 Correct 23 ms 6100 KB Output is correct
4 Correct 13 ms 4148 KB Output is correct
5 Correct 10 ms 3380 KB Output is correct
6 Correct 12 ms 3452 KB Output is correct
7 Correct 11 ms 3392 KB Output is correct
8 Correct 11 ms 3384 KB Output is correct
9 Correct 11 ms 3380 KB Output is correct
10 Incorrect 12 ms 4160 KB Wrong Answer [7]
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6284 KB Output is correct
2 Correct 20 ms 6440 KB Output is correct
3 Correct 19 ms 6164 KB Output is correct
4 Correct 16 ms 4152 KB Output is correct
5 Correct 11 ms 3384 KB Output is correct
6 Correct 13 ms 3384 KB Output is correct
7 Correct 13 ms 3384 KB Output is correct
8 Correct 11 ms 3372 KB Output is correct
9 Correct 11 ms 3324 KB Output is correct
10 Incorrect 11 ms 4164 KB Wrong Answer [7]
11 Halted 0 ms 0 KB -