oj.uz

Submission #842017

# Submission time Handle Problem Language Result Execution time Memory
842017 2023-09-02T10:12:55 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
70 / 100
 1000 ms 8024 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define in insert
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define deb(x) cout << #x << " = " << x << '\n';
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;

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

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 5e4 + 3;

int n, q, a[10], dis[N], pref[N], w[N];
bool arr[N];
vector <pair <pii, int>> g[N];
bitset <N> used, cur;

void dfs2(int v, int p) {
	for(auto to:g[v]) {
		if(to.ff.ff == p) continue;
		dis[to.ff.ff] = dis[v] + 1;
		pref[dis[to.ff.ff]] = pref[dis[v]] + to.ff.ss;
		dfs2(to.ff.ff, v);
	}
}

void dfs(int v, int p) {
	if(arr[v]) used |= cur;
	for(auto to:g[v]) {
		if(to.ff.ff == p) continue;
		cur[to.ss] = 1;
		dfs(to.ff.ff, v);
		cur[to.ss] = 0;
	}
}

void solve() {
	cin >> n;
	int sum = 0;
	bool sub2 = 1;
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v >> w[i];
		u++;
		v++;
		sum += w[i];
		g[u].pb({{v, w[i]}, i});
		g[v].pb({{u, w[i]}, i});
		if(sz(g[u]) > 2 || sz(g[v]) > 2) sub2 = 0;
	}
	cin >> q;
	if(n == 5 && q == 1) {
		cout << sum << '\n';
		return;
	}
	if(sub2) {
		int root;
		for(int i = 1; i <= n; i++) {
			if(sz(g[i]) == 1) {
				root = i;
				break;
			}
		}
		dis[root] = 1;
		dfs2(root, root);
		while(q--) {
			int l = inf, r = -inf;
			for(int i = 1; i <= 5; i++) {
				cin >> a[i];
				a[i]++;
				l = min(l, dis[a[i]]);
				r = max(r, dis[a[i]]);
			}
			cout << pref[r] - pref[l] << '\n';
		}
		return;
	}
	while(q--) {
		for(int i = 1; i <= 5; i++) {
			cin >> a[i];
			a[i]++;
			arr[a[i]] = 1;
		}
		for(int i = 1; i <= 5; i++) {
			dfs(a[i], -1);
		}
		int ans = 0;
		for(int i = 1; i < n; i++) {
			if(used[i]) ans += w[i];
		}
		cout << ans << '\n';
		used.reset();
		for(int i = 1; i <= 5; i++) {
			arr[a[i]] = 0;
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int TT = 1;
	// cin >> TT;
	while(TT--) {
		solve();
	}
	return 0;
}

Compilation message

roadsideadverts.cpp: In function 'void solve()':
roadsideadverts.cpp:74:7: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |   dfs2(root, root);
      |   ~~~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7784 KB Output is correct
2 Correct 24 ms 7740 KB Output is correct
3 Correct 20 ms 8024 KB Output is correct
4 Correct 25 ms 7624 KB Output is correct
5 Correct 20 ms 7772 KB Output is correct
6 Correct 22 ms 7764 KB Output is correct
7 Correct 20 ms 7768 KB Output is correct
8 Correct 20 ms 7772 KB Output is correct
9 Correct 22 ms 7764 KB Output is correct
10 Correct 20 ms 7772 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 3992 KB Output is correct
2 Correct 899 ms 6844 KB Output is correct
3 Correct 912 ms 6816 KB Output is correct
4 Correct 910 ms 7088 KB Output is correct
5 Correct 937 ms 7068 KB Output is correct
6 Correct 975 ms 7080 KB Output is correct
7 Correct 929 ms 7000 KB Output is correct
8 Correct 915 ms 6832 KB Output is correct
9 Correct 917 ms 6832 KB Output is correct
10 Correct 911 ms 6988 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 18 ms 7784 KB Output is correct
3 Correct 24 ms 7740 KB Output is correct
4 Correct 20 ms 8024 KB Output is correct
5 Correct 25 ms 7624 KB Output is correct
6 Correct 20 ms 7772 KB Output is correct
7 Correct 22 ms 7764 KB Output is correct
8 Correct 20 ms 7768 KB Output is correct
9 Correct 20 ms 7772 KB Output is correct
10 Correct 22 ms 7764 KB Output is correct
11 Correct 20 ms 7772 KB Output is correct
12 Correct 563 ms 3992 KB Output is correct
13 Correct 899 ms 6844 KB Output is correct
14 Correct 912 ms 6816 KB Output is correct
15 Correct 910 ms 7088 KB Output is correct
16 Correct 937 ms 7068 KB Output is correct
17 Correct 975 ms 7080 KB Output is correct
18 Correct 929 ms 7000 KB Output is correct
19 Correct 915 ms 6832 KB Output is correct
20 Correct 917 ms 6832 KB Output is correct
21 Correct 911 ms 6988 KB Output is correct
22 Correct 18 ms 7768 KB Output is correct
23 Execution timed out 1060 ms 4076 KB Time limit exceeded
24 Halted 0 ms 0 KB -