oj.uz

Submission #377835

# Submission time Handle Problem Language Result Execution time Memory
377835 2021-03-15T08:31:48 Z pit4h Designated Cities (JOI19_designated_cities) C++14
0 / 100
 2000 ms 15868 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
const int MAXN = 2e5+1;
const ll INF = 1e18+1;
int n, a[MAXN], b[MAXN], c[MAXN], d[MAXN];
ll total;
vector<pii> g[MAXN];

pii get_furthest(int x, int p, ll dist) {
	pii res = mp(dist, x);
	for(auto& [i, w]: g[x]) {
		if(i!=p) {
			res = max(res, get_furthest(i, x, dist+w));
		}
	}
	return res;
}
ll get_score(int x, int p) {
	ll res = 0;
	for(auto& [i, w]: g[x]) {
		if(i!=p) {
			res += get_score(i, x);
		}
		else {
			res += w;
		}
	}
	return res;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=0; i<n-1; ++i) {
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		g[a[i]].push_back(mp(b[i], c[i]));
		g[b[i]].push_back(mp(a[i], d[i]));
		total += c[i]+d[i];
	}
	ll ans = 0;
	for(int i=1; i<=n; ++i) {
		int root = i;
		ll score = get_score(root, root);	
		score += get_furthest(root, root, 0).st;
		ans = max(ans, score);
	}

	int q; cin>>q;
	for(int i=0; i<q; ++i) {
		int e; cin>>e;
		if(e==2) cout<<total - ans<<'\n';
		else cout<<-1<<'\n';
	}
}

Compilation message

designated_cities.cpp: In function 'pii get_furthest(int, int, ll)':
designated_cities.cpp:16:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |  for(auto& [i, w]: g[x]) {
      |            ^
designated_cities.cpp: In function 'll get_score(int, int)':
designated_cities.cpp:25:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |  for(auto& [i, w]: g[x]) {
      |            ^

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Execution timed out 2066 ms 15868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

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