Submission #118075

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
118075	2019-06-18T06:40:26 Z	김세빈(#2888)	Designated Cities (JOI19_designated_cities)	C++14	9 / 100	585 ms	40772 KB

designated_cities

#include <bits/stdc++.h>

using namespace std;

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

vector <pll> V[202020];
ll n, ans, k;

pll dfs(ll p, ll r, ll d)
{
	pll ret = pll(d, p);
	
	for(pll &t: V[p]){
		if(t.first != r){
			ret = max(ret, dfs(t.first, p, d + t.second));
		}
	}
	
	return ret;
}

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

void dfs3(ll p, ll r, ll d, ll x)
{
	if(p == x) ans -= d;
	
	for(pll &t: V[p]){
		if(t.first != r){
			dfs3(t.first, p, d + t.second, x);
		}
	}
}

int main()
{
	ll q, i, u, v, x, y, p, d;
	
	scanf("%lld", &n);
	
	for(i=1; i<n; i++){
		scanf("%lld%lld%lld%lld", &u, &v, &x, &y);
		V[u].emplace_back(v, x);
		V[v].emplace_back(u, y);
	}
	
	scanf("%lld", &q);
	
	if(q != 1) return 0;
	
	tie(d, u) = dfs(1, 0, 0);
	tie(d, v) = dfs(u, 0, 0);
	
	dfs3(u, 0, 0, v); dfs3(v, 0, 0, u);
	
	dfs2(u, 0); dfs2(v, 0);
	
	printf("%lld\n", ans / 2);
	
	return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:47:23: warning: unused variable 'p' [-Wunused-variable]
  ll q, i, u, v, x, y, p, d;
                       ^
designated_cities.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:52: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:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &q);
  ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

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

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	5120 KB	Output is correct
2	Correct	413 ms	15312 KB	Output is correct
3	Correct	585 ms	40772 KB	Output is correct
4	Correct	408 ms	20500 KB	Output is correct
5	Correct	420 ms	22172 KB	Output is correct
6	Correct	455 ms	25128 KB	Output is correct
7	Correct	248 ms	20936 KB	Output is correct
8	Correct	552 ms	33972 KB	Output is correct
9	Correct	212 ms	20804 KB	Output is correct