oj.uz

Submission #114311

# Submission time Handle Problem Language Result Execution time Memory
114311 2019-05-31T19:35:37 Z tincamatei Designated Cities (JOI19_designated_cities) C++14
7 / 100
 411 ms 31224 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000;

struct Edge {
	int a, b, c, d;
	
	int other(int nod) {
		return a ^ b ^ nod;
	}

	int cost(int src) {
		if(src == a)
			return c;
		else
			return d;
	}
} edges[MAX_N - 1];

vector<int> graph[1+MAX_N];
long long rez[1+MAX_N];

void calcRoot(int nod, int papa = 0) {
	for(auto it: graph[nod]) {
		int son = edges[it].other(nod);
		if(son != papa) {
			rez[1] += edges[it].cost(nod);
			calcRoot(son, nod);
		}
	}
}

long long calcBestPathFor1(int nod, int papa = 0, long long extra = 0LL) {
	long long rez = extra;
	for(auto it: graph[nod]) {
		int son = edges[it].other(nod);
		if(son != papa) {
			long long sonRez = calcBestPathFor1(son, nod, extra - edges[it].cost(nod) + edges[it].cost(son));
			rez = min(rez, sonRez);
		}
	}
	return rez;
}

int main() {
	int N, Q;
	int leaves = 0;

	scanf("%d", &N);
	for(int i = 0; i < N - 1; ++i) {
		scanf("%d%d%d%d", &edges[i].a, &edges[i].b, &edges[i].c, &edges[i].d);
		graph[edges[i].a].push_back(i);
		graph[edges[i].b].push_back(i);
	}

	for(int i = 1; i <= N; ++i)
		if(graph[i].size() == 1)
			++leaves;
	
	rez[1] = calcBestPathFor1(1);
	calcRoot(1);

	scanf("%d", &Q);
	for(int i = 0; i < Q; ++i) {
		int x;
		scanf("%d", &x);
		printf("%lld\n", rez[x]);
	}
	return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &edges[i].a, &edges[i].b, &edges[i].c, &edges[i].d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 286 ms 20984 KB Output is correct
3 Correct 386 ms 31224 KB Output is correct
4 Correct 297 ms 19576 KB Output is correct
5 Correct 287 ms 20980 KB Output is correct
6 Correct 318 ms 22264 KB Output is correct
7 Correct 249 ms 21388 KB Output is correct
8 Correct 411 ms 31224 KB Output is correct
9 Correct 179 ms 21736 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Incorrect 317 ms 21108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 286 ms 20984 KB Output is correct
3 Correct 386 ms 31224 KB Output is correct
4 Correct 297 ms 19576 KB Output is correct
5 Correct 287 ms 20980 KB Output is correct
6 Correct 318 ms 22264 KB Output is correct
7 Correct 249 ms 21388 KB Output is correct
8 Correct 411 ms 31224 KB Output is correct
9 Correct 179 ms 21736 KB Output is correct
10 Correct 8 ms 4992 KB Output is correct
11 Incorrect 317 ms 21108 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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