oj.uz

Submission #260457

# Submission time Handle Problem Language Result Execution time Memory
260457 2020-08-10T10:03:40 Z patrikpavic2 Designated Cities (JOI19_designated_cities) C++17
22 / 100
 366 ms 33148 KB 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#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], v2[N];

ll C[N], uk, sol1, sol2, solt, sol[N];
int n, bio[20];

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;
}

void dfs3(int x, int lst){
	for(pip &nxt : v2[x]){
		if(nxt.X == lst) continue;
		solt += nxt.Y.X; nxt.Y.X = 0;
		dfs3(nxt.X, x);
	}
}

void odradi(int msk){
	for(int i = 1;i <= n;i++)
		v2[i] = v[i];
	solt = 0; int kol = 0;
	for(int i = 1;i <= n;i++){
		if(msk & (1 << (i - 1)))
			dfs3(i, i), kol++;
	}
	sol[kol] = max(sol[kol], solt);	
}

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(n <= 16){
		for(int i = 0;i < (1 << n);i++)
			odradi(i);
		for(;q--;){
			int x; scanf("%d", &x);
			printf("%lld\n", uk - sol[x]);
		}
		return 0;
	}
	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:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:72: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:76: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:81:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x);
           ~~~~~^~~~~~~~~~
designated_cities.cpp:87: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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 70 ms 9728 KB Output is correct
3 Correct 75 ms 9848 KB Output is correct
4 Correct 66 ms 9728 KB Output is correct
5 Correct 67 ms 9728 KB Output is correct
6 Correct 67 ms 9728 KB Output is correct
7 Correct 70 ms 9728 KB Output is correct
8 Correct 66 ms 9728 KB Output is correct
9 Correct 66 ms 9728 KB Output is correct
10 Correct 77 ms 9848 KB Output is correct
11 Correct 73 ms 9728 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 272 ms 20332 KB Output is correct
3 Correct 307 ms 26016 KB Output is correct
4 Correct 251 ms 20216 KB Output is correct
5 Correct 268 ms 20144 KB Output is correct
6 Correct 283 ms 21320 KB Output is correct
7 Correct 240 ms 20136 KB Output is correct
8 Correct 310 ms 26360 KB Output is correct
9 Correct 180 ms 20536 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 322 ms 20216 KB Output is correct
3 Correct 366 ms 33148 KB Output is correct
4 Correct 290 ms 20472 KB Output is correct
5 Correct 283 ms 20016 KB Output is correct
6 Correct 307 ms 22264 KB Output is correct
7 Correct 201 ms 20388 KB Output is correct
8 Correct 333 ms 27768 KB Output is correct
9 Correct 190 ms 20400 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 70 ms 9728 KB Output is correct
3 Correct 75 ms 9848 KB Output is correct
4 Correct 66 ms 9728 KB Output is correct
5 Correct 67 ms 9728 KB Output is correct
6 Correct 67 ms 9728 KB Output is correct
7 Correct 70 ms 9728 KB Output is correct
8 Correct 66 ms 9728 KB Output is correct
9 Correct 66 ms 9728 KB Output is correct
10 Correct 77 ms 9848 KB Output is correct
11 Correct 73 ms 9728 KB Output is correct
12 Correct 6 ms 9764 KB Output is correct
13 Incorrect 7 ms 9856 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 272 ms 20332 KB Output is correct
3 Correct 307 ms 26016 KB Output is correct
4 Correct 251 ms 20216 KB Output is correct
5 Correct 268 ms 20144 KB Output is correct
6 Correct 283 ms 21320 KB Output is correct
7 Correct 240 ms 20136 KB Output is correct
8 Correct 310 ms 26360 KB Output is correct
9 Correct 180 ms 20536 KB Output is correct
10 Correct 7 ms 9856 KB Output is correct
11 Correct 322 ms 20216 KB Output is correct
12 Correct 366 ms 33148 KB Output is correct
13 Correct 290 ms 20472 KB Output is correct
14 Correct 283 ms 20016 KB Output is correct
15 Correct 307 ms 22264 KB Output is correct
16 Correct 201 ms 20388 KB Output is correct
17 Correct 333 ms 27768 KB Output is correct
18 Correct 190 ms 20400 KB Output is correct
19 Correct 7 ms 9728 KB Output is correct
20 Incorrect 219 ms 18496 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 70 ms 9728 KB Output is correct
3 Correct 75 ms 9848 KB Output is correct
4 Correct 66 ms 9728 KB Output is correct
5 Correct 67 ms 9728 KB Output is correct
6 Correct 67 ms 9728 KB Output is correct
7 Correct 70 ms 9728 KB Output is correct
8 Correct 66 ms 9728 KB Output is correct
9 Correct 66 ms 9728 KB Output is correct
10 Correct 77 ms 9848 KB Output is correct
11 Correct 73 ms 9728 KB Output is correct
12 Correct 6 ms 9728 KB Output is correct
13 Correct 272 ms 20332 KB Output is correct
14 Correct 307 ms 26016 KB Output is correct
15 Correct 251 ms 20216 KB Output is correct
16 Correct 268 ms 20144 KB Output is correct
17 Correct 283 ms 21320 KB Output is correct
18 Correct 240 ms 20136 KB Output is correct
19 Correct 310 ms 26360 KB Output is correct
20 Correct 180 ms 20536 KB Output is correct
21 Correct 7 ms 9856 KB Output is correct
22 Correct 322 ms 20216 KB Output is correct
23 Correct 366 ms 33148 KB Output is correct
24 Correct 290 ms 20472 KB Output is correct
25 Correct 283 ms 20016 KB Output is correct
26 Correct 307 ms 22264 KB Output is correct
27 Correct 201 ms 20388 KB Output is correct
28 Correct 333 ms 27768 KB Output is correct
29 Correct 190 ms 20400 KB Output is correct
30 Correct 6 ms 9764 KB Output is correct
31 Incorrect 7 ms 9856 KB Output isn't correct
32 Halted 0 ms 0 KB -