답안 #377842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377842	2021-03-15T09:44:58 Z	pit4h	Designated Cities (JOI19_designated_cities)	C++14	9 / 100	454 ms	39788 KB

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];

pair<ll, int> get_furthest(int x, int p, ll dist) {
	pair<ll, int> 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

designated_cities.cpp: In function 'std::pair<long long int, int> 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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	5100 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	5100 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	358 ms	15616 KB	Output is correct
3	Correct	454 ms	39788 KB	Output is correct
4	Correct	356 ms	20684 KB	Output is correct
5	Correct	390 ms	22092 KB	Output is correct
6	Correct	370 ms	24940 KB	Output is correct
7	Correct	201 ms	22364 KB	Output is correct
8	Correct	427 ms	33516 KB	Output is correct
9	Correct	187 ms	22108 KB	Output is correct