oj.uz

Submission #910171

# Submission time Handle Problem Language Result Execution time Memory
910171 2024-01-18T00:59:05 Z Maaxle Amusement Park (JOI17_amusement_park) C++17
0 / 100
 20 ms 5232 KB 
#include <bits/stdc++.h>
#include "Joi.h"

#define ll long long
#define range(i, a, b) for (ll i = a; i < b; i++)
#define all(x) begin(x), end(x)
#define INF ((ll) 1 << 60)
#define pqueue priority_queue

using namespace std;

ll x;
vector<vector<ll>> adj;
vector<bool> memo;

void dfs (ll i, ll dig) {
	memo[i] = 1;
	MessageBoard(i, (int) ((x & (1ll << dig)) > 0));
	for (ll k : adj[i]) {
		if (!memo[k])
			dfs(k, (dig + 1) % 60);
	}
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	adj.resize(N);
	memo.resize(N);
	x = X;

	range(i, 0, M) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(0, 0);
}
#include <bits/stdc++.h>
#include "Ioi.h"

#define ll long long
#define range(i, a, b) for (ll i = a; i < b; i++)
#define all(x) begin(x), end(x)
#define INF ((ll) 1 << 60)
#define pqueue priority_queue

using namespace std;

struct TPos {
	ll node, dig;
};
bool operator < (const TPos& i, const TPos& j) { return i.node < j.node; }

ll v;
ll v_it = -1;
vector<vector<ll>> adj;
vector<bool> memo;
vector<ll> path;
vector<TPos> pre;

void dfs (ll i) {
	memo[i] = 1;
	path.push_back(i);

	if (i == v && v_it == -1)
		v_it = path.size() - 1;

	if (pre.empty())
		pre.push_back({i, 0});
	else 
		pre.push_back({i, (pre.back().dig + 1) % 60});

	for (ll k : adj[i]) {
		if (!memo[k])
			dfs(k);
	}

	if (path.back() != i)
		path.push_back(i);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	adj.resize(N);
	memo.resize(N);
	v = V;

	range(i, 0, M) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(0);
	sort(all(pre));

	vector<ll> freq (60);
	ll l = v_it, r = v_it;
	freq[pre[path[v_it]].dig]++;
	ll cnt = 1;
	while (r < path.size() - 1 && r - v + 1 < 120) {
		r++;
		freq[pre[path[r]].dig]++;
		if (freq[pre[path[r]].dig] == 1) cnt++;
	}

	while (l > 0 && r - l + 1 < 120) {
		l--;
		freq[pre[path[l]].dig]++;
		if (freq[pre[path[l]].dig] == 1) cnt++;
	}

	while (cnt < 60) {
		l--;
		freq[pre[path[l]].dig]++;
		if (freq[pre[path[l]].dig] == 1) cnt++;

		freq[pre[path[r]].dig]--;
		if (freq[pre[path[r]].dig] == 0) cnt--;
		r--;
	}

	ll ans = 0;
	range(i, v_it, r + 1) {
		if (path[i] == v) {
			ans |= ((ll) P << pre[path[i]].dig);
			continue;
		}
		ans |= (Move(path[i]) << pre[path[i]].dig);
	}

	for (ll i = r - 1; i >= r; i++) {
		if (path[i] == v) {
			ans |= ((ll) P << pre[path[i]].dig);
			continue;
		}
		ans |= (Move(path[i]) << pre[path[i]].dig);
	}

	return ans;
}

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:61:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  while (r < path.size() - 1 && r - v + 1 < 120) {
      |         ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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