oj.uz

Submission #260454

# Submission time Handle Problem Language Result Execution time Memory
260454 2020-08-10T09:58:52 Z patrikpavic2 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 335 ms 34040 KB 
#include <cstdio>
#include <cstring>
#include <vector>

#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 < pip > v[N];

ll C[N], uk, sol1, sol2;
int n;

void start(int x, int lst){
	for(pip nxt : v[x]){
		if(nxt.X == lst) continue;
		C[1] += nxt.Y.X; start(nxt.X, x);
	}
}

void dfs(int x, int lst){
	for(pip nxt : v[x]){
		if(nxt.X == lst) continue;
		C[nxt.X] = C[x] - nxt.Y.X + nxt.Y.Y;
		dfs(nxt.X, x);
	}
	sol1 = max(sol1, C[x]);
}

ll dfs2(int x, int lst){
	ll dos = C[x];
	for(pip nxt : v[x]){
		if(nxt.X == lst) continue;
		ll sad = dfs2(nxt.X, x) + nxt.Y.X + nxt.Y.Y;
		sol2 = max(sol2, dos + sad);
		dos = max(dos, sad);
	}	
	return dos;
}

int main(){
	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, b}}); v[y].PB({x, {b, a}});
		uk += a + b;
	}
	int q; scanf("%d", &q);
	if(q > 1) return 0;
	int kol; scanf("%d", &kol);
	if(kol > 2) return 0;
	start(1, 1); dfs(1, 1);
	if(kol == 1){
		printf("%lld\n", uk - sol1);
	}
	else{
		dfs2(1, 1);
		printf("%lld\n", uk - sol2 / 2);
	}
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:52:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, a, b; scanf("%d%d%d%d", &x, &y, &b, &a);
                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf("%d", &q);
         ~~~~~^~~~~~~~~~
designated_cities.cpp:58:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int kol; scanf("%d", &kol);
           ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 281 ms 21276 KB Output is correct
3 Correct 308 ms 26872 KB Output is correct
4 Correct 271 ms 19960 KB Output is correct
5 Correct 265 ms 21164 KB Output is correct
6 Correct 284 ms 22264 KB Output is correct
7 Correct 248 ms 21160 KB Output is correct
8 Correct 305 ms 27352 KB Output is correct
9 Correct 205 ms 21664 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 298 ms 21252 KB Output is correct
3 Correct 333 ms 34040 KB Output is correct
4 Correct 279 ms 19932 KB Output is correct
5 Correct 286 ms 21168 KB Output is correct
6 Correct 302 ms 23288 KB Output is correct
7 Correct 203 ms 21416 KB Output is correct
8 Correct 335 ms 29048 KB Output is correct
9 Correct 186 ms 21284 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 281 ms 21276 KB Output is correct
3 Correct 308 ms 26872 KB Output is correct
4 Correct 271 ms 19960 KB Output is correct
5 Correct 265 ms 21164 KB Output is correct
6 Correct 284 ms 22264 KB Output is correct
7 Correct 248 ms 21160 KB Output is correct
8 Correct 305 ms 27352 KB Output is correct
9 Correct 205 ms 21664 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 298 ms 21252 KB Output is correct
12 Correct 333 ms 34040 KB Output is correct
13 Correct 279 ms 19932 KB Output is correct
14 Correct 286 ms 21168 KB Output is correct
15 Correct 302 ms 23288 KB Output is correct
16 Correct 203 ms 21416 KB Output is correct
17 Correct 335 ms 29048 KB Output is correct
18 Correct 186 ms 21284 KB Output is correct
19 Correct 4 ms 4992 KB Output is correct
20 Incorrect 216 ms 19568 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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