Submission #377823

#	Time	Username	Problem	Language	Result	Execution time	Memory
377823		pit4h	Designated Cities (JOI19_designated_cities)	C++14	0 / 100	374 ms	15724 KiB

designated_cities

#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];
	}
	int root = get_furthest(1, 1, 0).nd;
	ll score = get_score(root, root);	
	score += get_furthest(root, root, 0).st;

	int r1 = get_furthest(root, root, 0).nd;
	ll s1 = get_score(r1, r1) + get_furthest(r1, r1, 0).st;
	int q; cin>>q;
	for(int i=0; i<q; ++i) {
		int e; cin>>e;
		if(e==2) cout<<total - max(score, s1)<<'\n';
		else cout<<-1<<'\n';
	}
}

Compilation message (stderr)

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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44