Submission #118091

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
118091	2019-06-18T07:20:39 Z	김세빈(#2888)	Designated Cities (JOI19_designated_cities)	C++14	9 / 100	356 ms	24156 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];
vector <ll> X, Y;
ll P[202020], D[202020], A[202020];
bool chk[202020];
ll n, ans;

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] ++;
	}
	
	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);
		if(x == 1) return 1 / 0;
		printf("%lld\n", A[x]);
	}
	
	return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:60:23: warning: division by zero [-Wdiv-by-zero]
   if(x == 1) return 1 / 0;
                     ~~^~~
designated_cities.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:22: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:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &q);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:59: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	Runtime error	12 ms	9984 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	12 ms	9984 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	5120 KB	Output is correct
2	Correct	356 ms	21444 KB	Output is correct
3	Correct	241 ms	17656 KB	Output is correct
4	Correct	332 ms	21376 KB	Output is correct
5	Correct	348 ms	21468 KB	Output is correct
6	Correct	330 ms	21604 KB	Output is correct
7	Correct	255 ms	24156 KB	Output is correct
8	Correct	288 ms	21356 KB	Output is correct
9	Correct	234 ms	24032 KB	Output is correct