Submission #118093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
118093	2019-06-18T07:26:14 Z	김세빈(#2888)	Designated Cities (JOI19_designated_cities)	C++14	9 / 100	592 ms	43556 KB

designated_cities

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

priority_queue <pll, vector <pll>, greater <pll>> Q;
vector <pll> V[202020], V2[202020];
vector <ll> X, Y;
ll P[202020], D[202020], A[202020];
bool chk[202020];
ll n, ans;

void dfs1(ll p, ll r)
{
	for(pll &t: V2[p]){
		if(t.first != r){
			ans += t.second;
			dfs1(t.first, p);
		}
	}
}

void dfs2(ll p, ll r)
{
	ll i;
	
	A[1] = min(A[1], ans);
	
	for(i=0; i<V2[p].size(); i++){
		if(V2[p][i].first != r){
			ans -= V2[p][i].second;
			ans += V[p][i].second;
			
			dfs2(V[p][i].first, p);
			
			ans += V2[p][i].second;
			ans += V[p][i].second;
		}
	}
}

int main()
{
	ll q, i, u, v, x, y, d;
	
	scanf("%lld", &n);
	
	for(i=1; i<n; i++){
		scanf("%lld%lld%lld%lld", &u, &v, &x, &y);
		V[u].emplace_back(v, y);
		V[v].emplace_back(u, x);
		D[u] ++; D[v] ++;
		
		V2[u].emplace_back(v, x);
		V2[v].emplace_back(u, y);
	}
	
	A[1] = 1e18;
	
	dfs1(1, 0);
	dfs2(1, 0);
	
	ans = 0;
	
	for(i=1; i<=n; i++){
		if(D[i] == 1){
			P[i] = V[i][0].first; chk[i] = 1;
			Q.push(pll(V[i][0].second, i));
		}
	}
	
	for(; Q.size() > 2; ){
		tie(d, u) = Q.top(); Q.pop();
		if(D[P[u]] == 2){
			chk[P[u]] = 1;
			
			for(pll &t: V[P[u]]){
				if(!chk[t.first]){
					d += t.second;
					P[u] = t.first;
					Q.push(pll(d, u));
					break;
				}
			}
		}
		else{
			ans += d;
			A[Q.size()] = ans;
			D[P[u]] --;
		}
	}
	
	scanf("%lld", &q);
	
	for(; q--; ){
		scanf("%lld", &x);
		printf("%lld\n", A[x]);
	}
	
	return 0;
}

Compilation message

designated_cities.cpp: In function 'void dfs2(ll, ll)':
designated_cities.cpp:31:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V2[p].size(); i++){
           ~^~~~~~~~~~~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &u, &v, &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &q);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9856 KB	Output is correct
2	Incorrect	10 ms	9856 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9856 KB	Output is correct
2	Incorrect	554 ms	36452 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	9856 KB	Output is correct
2	Correct	592 ms	35880 KB	Output is correct
3	Correct	560 ms	43556 KB	Output is correct
4	Correct	544 ms	35784 KB	Output is correct
5	Correct	563 ms	36044 KB	Output is correct
6	Correct	578 ms	37968 KB	Output is correct
7	Correct	362 ms	37920 KB	Output is correct
8	Correct	581 ms	42604 KB	Output is correct
9	Correct	329 ms	37648 KB	Output is correct