oj.uz

Submission #263233

# Submission time Handle Problem Language Result Execution time Memory
263233 2020-08-13T14:22:04 Z patrikpavic2 Designated Cities (JOI19_designated_cities) C++17
13 / 100
 625 ms 45976 KB 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <set>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;
typedef pair < int, pii > pip;

const int N = 2e5 + 500;

vector < pii > v[N];
vector < pip > v2[N];

set < pii > S;

int n, deg[N], bio[N];
ll cur, bst[N];
ll C[N], uk;
 
void start(int x, int lst){
	for(pip nxt : v2[x]){
		if(nxt.X == lst) continue;
		C[1] += nxt.Y.X; start(nxt.X, x);
	}
}
 
void dfs(int x, int lst){
	for(pip nxt : v2[x]){
		if(nxt.X == lst) continue;
		C[nxt.X] = C[x] - nxt.Y.X + nxt.Y.Y;
		dfs(nxt.X, x);
	}
	bst[1] = max(bst[1], C[x]);
}

inline int pronadi(int x){
	for(pii nxt : v[x])
		if(deg[nxt.X])
			return nxt.Y;
	return 0;
}


int main(){
	for(int i = 0;i < N;i++)
		bst[i] = 1e18;
	scanf("%d", &n);
	for(int i = 1;i < n;i++){
		int x, y, a, b; scanf("%d%d%d%d", &x, &y, &b, &a);
		v[x].PB({y, a}); v[y].PB({x, b});
		v2[x].PB({y, {a, b}}); v2[y].PB({x, {b, a}});
		uk += a + b;
		deg[x]++; deg[y]++;
	}
	for(int i = 1;i <= n;i++){
		if(deg[i] == 1)
			S.insert({v[i][0].Y, i});
	}
	bst[(int)S.size()] = cur;
	int lisce = (int)S.size();
	for(;S.size() > 2;){
		int brs = S.begin() -> Y; 
		int tez = S.begin() -> X;
		deg[brs] = 0;
		S.erase(S.begin());
		for(pii nxt : v[brs]){
			if(deg[nxt.X] > 0){
				deg[nxt.X]--;
				if(deg[nxt.X] == 1)
					S.insert({pronadi(nxt.X) + tez, nxt.X});
				else
					bst[(int)S.size()] = bst[(int)S.size() + 1] + tez;
				break;
			}
		}
	}
	bst[1] = 0;
	start(1, 1); dfs(1, 1);
	bst[1] = uk - bst[1];
	int q; scanf("%d", &q);
	for(;q--;){
		int x; scanf("%d", &x);
		x = min(x, lisce);
		printf("%lld\n", bst[x]);
	}
	
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
designated_cities.cpp:57:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   int x, y, a, b; scanf("%d%d%d%d", &x, &y, &b, &a);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
designated_cities.cpp:90:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |   int x; scanf("%d", &x);
      |          ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11264 KB Output is correct
2 Correct 7 ms 11264 KB Output is correct
3 Correct 8 ms 11264 KB Output is correct
4 Correct 8 ms 11264 KB Output is correct
5 Correct 8 ms 11264 KB Output is correct
6 Correct 7 ms 11264 KB Output is correct
7 Correct 7 ms 11368 KB Output is correct
8 Correct 9 ms 11264 KB Output is correct
9 Correct 9 ms 11264 KB Output is correct
10 Correct 9 ms 11264 KB Output is correct
11 Correct 8 ms 11264 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11264 KB Output is correct
2 Correct 625 ms 39588 KB Output is correct
3 Correct 475 ms 40312 KB Output is correct
4 Correct 531 ms 38036 KB Output is correct
5 Correct 559 ms 39848 KB Output is correct
6 Correct 614 ms 40440 KB Output is correct
7 Correct 581 ms 41632 KB Output is correct
8 Correct 484 ms 41608 KB Output is correct
9 Correct 473 ms 45976 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11296 KB Output is correct
2 Incorrect 576 ms 39544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11264 KB Output is correct
2 Correct 7 ms 11264 KB Output is correct
3 Correct 8 ms 11264 KB Output is correct
4 Correct 8 ms 11264 KB Output is correct
5 Correct 8 ms 11264 KB Output is correct
6 Correct 7 ms 11264 KB Output is correct
7 Correct 7 ms 11368 KB Output is correct
8 Correct 9 ms 11264 KB Output is correct
9 Correct 9 ms 11264 KB Output is correct
10 Correct 9 ms 11264 KB Output is correct
11 Correct 8 ms 11264 KB Output is correct
12 Correct 7 ms 11264 KB Output is correct
13 Incorrect 10 ms 11648 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11264 KB Output is correct
2 Correct 625 ms 39588 KB Output is correct
3 Correct 475 ms 40312 KB Output is correct
4 Correct 531 ms 38036 KB Output is correct
5 Correct 559 ms 39848 KB Output is correct
6 Correct 614 ms 40440 KB Output is correct
7 Correct 581 ms 41632 KB Output is correct
8 Correct 484 ms 41608 KB Output is correct
9 Correct 473 ms 45976 KB Output is correct
10 Correct 7 ms 11296 KB Output is correct
11 Incorrect 576 ms 39544 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11264 KB Output is correct
2 Correct 7 ms 11264 KB Output is correct
3 Correct 8 ms 11264 KB Output is correct
4 Correct 8 ms 11264 KB Output is correct
5 Correct 8 ms 11264 KB Output is correct
6 Correct 7 ms 11264 KB Output is correct
7 Correct 7 ms 11368 KB Output is correct
8 Correct 9 ms 11264 KB Output is correct
9 Correct 9 ms 11264 KB Output is correct
10 Correct 9 ms 11264 KB Output is correct
11 Correct 8 ms 11264 KB Output is correct
12 Correct 8 ms 11264 KB Output is correct
13 Correct 625 ms 39588 KB Output is correct
14 Correct 475 ms 40312 KB Output is correct
15 Correct 531 ms 38036 KB Output is correct
16 Correct 559 ms 39848 KB Output is correct
17 Correct 614 ms 40440 KB Output is correct
18 Correct 581 ms 41632 KB Output is correct
19 Correct 484 ms 41608 KB Output is correct
20 Correct 473 ms 45976 KB Output is correct
21 Correct 7 ms 11296 KB Output is correct
22 Incorrect 576 ms 39544 KB Output isn't correct
23 Halted 0 ms 0 KB -