oj.uz

Submission #841975

# Submission time Handle Problem Language Result Execution time Memory
841975 2023-09-02T09:37:02 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 26 ms 7552 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 + 5;

int n, q, a[10], dis[N], pref[N];
vector <pii> g[N];

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

void solve() {
	cin >> n;
	int sum = 0;
	bool sub2 = 1;
	for(int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u++;
		v++;
		sum += w;
		g[u].pb({v, w});
		g[v].pb({u, w});
		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;
	}
}

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:62:7: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |   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 19 ms 7456 KB Output is correct
2 Correct 20 ms 7516 KB Output is correct
3 Correct 26 ms 7552 KB Output is correct
4 Correct 24 ms 7536 KB Output is correct
5 Correct 20 ms 7516 KB Output is correct
6 Correct 21 ms 7348 KB Output is correct
7 Correct 20 ms 7512 KB Output is correct
8 Correct 20 ms 7516 KB Output is correct
9 Correct 21 ms 7516 KB Output is correct
10 Correct 20 ms 7512 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 3492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 19 ms 7456 KB Output is correct
3 Correct 20 ms 7516 KB Output is correct
4 Correct 26 ms 7552 KB Output is correct
5 Correct 24 ms 7536 KB Output is correct
6 Correct 20 ms 7516 KB Output is correct
7 Correct 21 ms 7348 KB Output is correct
8 Correct 20 ms 7512 KB Output is correct
9 Correct 20 ms 7516 KB Output is correct
10 Correct 21 ms 7516 KB Output is correct
11 Correct 20 ms 7512 KB Output is correct
12 Incorrect 13 ms 3492 KB Output isn't correct
13 Halted 0 ms 0 KB -