oj.uz

Submission #226271

# Submission time Handle Problem Language Result Execution time Memory
226271 2020-04-23T09:09:49 Z _7_7_ Designated Cities (JOI19_designated_cities) C++14
100 / 100
 496 ms 46500 KB 
#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 3e5 + 11;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;


int n, q, a, b, c, d, e, sum, sumc, dp[N], res[N], cnt[N];
set < pii > Q;
bool was[N];


struct edge {
	int to, c, d;
	edge () {}
	edge (int _to, int _c, int _d) {
		to = _to;
		c = _c;
		d = _d;
	}
};
              

vector < edge > g[N];

void dfs (int v, int p = 0) {
	for (auto x : g[v]) 
		if (x.to != p) {
			dp[x.to] = dp[v] + x.c - x.d;
			dfs(x.to, v); 
			sumc += x.d;
		}
}

pii Find (int v) {
	for (auto x : g[v])
		if (!was[x.to]) 
			return {x.to, x.d};		
}

main () {
	scanf("%lld", &n);
	for (int i = 1; i < n; ++i)  {
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		g[a].pb(edge(b, c, d));
		g[b].pb(edge(a, d, c));
		sum += c;
		sum += d;
		++cnt[a], ++cnt[b];
	}

	dfs(1);
	res[1] = sum - (sumc + *max_element(dp + 1, dp + 1 + n));

	for (int i = 1; i <= n; ++i)
		if (cnt[i] == 1)
			Q.insert({Find(i).s, i});

	while (sz(Q) > 2) {
		int v = Q.begin()->s, u = Q.begin()->f;
		was[v] = 1;
		Q.erase(Q.begin());		
		int p = Find(v).f;
		--cnt[p];
		if (cnt[p] == 1) {
			int x = Find(p).s;
			Q.insert({x + u, p});
		} else
			res[sz(Q)] = res[sz(Q) + 1] + u;
	}


	scanf("%lld", &q);
	while (q--) {
		scanf("%lld", &e);
		printf("%lld\n", res[e]);
	}
}

Compilation message

designated_cities.cpp:74:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
designated_cities.cpp: In function 'pii Find(long long int)':
designated_cities.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &q);
  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &e);
   ~~~~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 434 ms 30476 KB Output is correct
3 Correct 284 ms 32504 KB Output is correct
4 Correct 383 ms 30584 KB Output is correct
5 Correct 434 ms 31272 KB Output is correct
6 Correct 423 ms 32036 KB Output is correct
7 Correct 430 ms 32676 KB Output is correct
8 Correct 294 ms 33784 KB Output is correct
9 Correct 361 ms 37016 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 419 ms 30584 KB Output is correct
3 Correct 288 ms 39032 KB Output is correct
4 Correct 397 ms 34552 KB Output is correct
5 Correct 466 ms 36564 KB Output is correct
6 Correct 452 ms 37460 KB Output is correct
7 Correct 394 ms 40984 KB Output is correct
8 Correct 340 ms 39544 KB Output is correct
9 Correct 363 ms 41880 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 9 ms 7424 KB Output is correct
9 Correct 8 ms 7296 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 9 ms 7424 KB Output is correct
12 Correct 8 ms 7424 KB Output is correct
13 Correct 10 ms 7680 KB Output is correct
14 Correct 10 ms 7680 KB Output is correct
15 Correct 11 ms 7680 KB Output is correct
16 Correct 13 ms 8064 KB Output is correct
17 Correct 11 ms 7680 KB Output is correct
18 Correct 11 ms 7680 KB Output is correct
19 Correct 11 ms 7680 KB Output is correct
20 Correct 12 ms 7680 KB Output is correct
21 Correct 11 ms 7680 KB Output is correct
22 Correct 11 ms 7680 KB Output is correct
23 Correct 11 ms 7680 KB Output is correct
24 Correct 13 ms 7936 KB Output is correct
25 Correct 11 ms 7808 KB Output is correct
26 Correct 11 ms 7808 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 434 ms 30476 KB Output is correct
3 Correct 284 ms 32504 KB Output is correct
4 Correct 383 ms 30584 KB Output is correct
5 Correct 434 ms 31272 KB Output is correct
6 Correct 423 ms 32036 KB Output is correct
7 Correct 430 ms 32676 KB Output is correct
8 Correct 294 ms 33784 KB Output is correct
9 Correct 361 ms 37016 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 419 ms 30584 KB Output is correct
12 Correct 288 ms 39032 KB Output is correct
13 Correct 397 ms 34552 KB Output is correct
14 Correct 466 ms 36564 KB Output is correct
15 Correct 452 ms 37460 KB Output is correct
16 Correct 394 ms 40984 KB Output is correct
17 Correct 340 ms 39544 KB Output is correct
18 Correct 363 ms 41880 KB Output is correct
19 Correct 8 ms 7552 KB Output is correct
20 Correct 442 ms 35936 KB Output is correct
21 Correct 282 ms 39032 KB Output is correct
22 Correct 385 ms 34552 KB Output is correct
23 Correct 436 ms 36344 KB Output is correct
24 Correct 409 ms 35116 KB Output is correct
25 Correct 435 ms 36216 KB Output is correct
26 Correct 419 ms 35192 KB Output is correct
27 Correct 436 ms 36500 KB Output is correct
28 Correct 426 ms 37240 KB Output is correct
29 Correct 418 ms 35704 KB Output is correct
30 Correct 404 ms 36012 KB Output is correct
31 Correct 410 ms 38820 KB Output is correct
32 Correct 334 ms 39800 KB Output is correct
33 Correct 363 ms 42264 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 9 ms 7424 KB Output is correct
9 Correct 8 ms 7296 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 9 ms 7424 KB Output is correct
12 Correct 8 ms 7424 KB Output is correct
13 Correct 434 ms 30476 KB Output is correct
14 Correct 284 ms 32504 KB Output is correct
15 Correct 383 ms 30584 KB Output is correct
16 Correct 434 ms 31272 KB Output is correct
17 Correct 423 ms 32036 KB Output is correct
18 Correct 430 ms 32676 KB Output is correct
19 Correct 294 ms 33784 KB Output is correct
20 Correct 361 ms 37016 KB Output is correct
21 Correct 8 ms 7424 KB Output is correct
22 Correct 419 ms 30584 KB Output is correct
23 Correct 288 ms 39032 KB Output is correct
24 Correct 397 ms 34552 KB Output is correct
25 Correct 466 ms 36564 KB Output is correct
26 Correct 452 ms 37460 KB Output is correct
27 Correct 394 ms 40984 KB Output is correct
28 Correct 340 ms 39544 KB Output is correct
29 Correct 363 ms 41880 KB Output is correct
30 Correct 8 ms 7424 KB Output is correct
31 Correct 10 ms 7680 KB Output is correct
32 Correct 10 ms 7680 KB Output is correct
33 Correct 11 ms 7680 KB Output is correct
34 Correct 13 ms 8064 KB Output is correct
35 Correct 11 ms 7680 KB Output is correct
36 Correct 11 ms 7680 KB Output is correct
37 Correct 11 ms 7680 KB Output is correct
38 Correct 12 ms 7680 KB Output is correct
39 Correct 11 ms 7680 KB Output is correct
40 Correct 11 ms 7680 KB Output is correct
41 Correct 11 ms 7680 KB Output is correct
42 Correct 13 ms 7936 KB Output is correct
43 Correct 11 ms 7808 KB Output is correct
44 Correct 11 ms 7808 KB Output is correct
45 Correct 8 ms 7552 KB Output is correct
46 Correct 442 ms 35936 KB Output is correct
47 Correct 282 ms 39032 KB Output is correct
48 Correct 385 ms 34552 KB Output is correct
49 Correct 436 ms 36344 KB Output is correct
50 Correct 409 ms 35116 KB Output is correct
51 Correct 435 ms 36216 KB Output is correct
52 Correct 419 ms 35192 KB Output is correct
53 Correct 436 ms 36500 KB Output is correct
54 Correct 426 ms 37240 KB Output is correct
55 Correct 418 ms 35704 KB Output is correct
56 Correct 404 ms 36012 KB Output is correct
57 Correct 410 ms 38820 KB Output is correct
58 Correct 334 ms 39800 KB Output is correct
59 Correct 363 ms 42264 KB Output is correct
60 Correct 8 ms 7424 KB Output is correct
61 Correct 484 ms 38648 KB Output is correct
62 Correct 329 ms 39476 KB Output is correct
63 Correct 427 ms 37240 KB Output is correct
64 Correct 488 ms 39052 KB Output is correct
65 Correct 477 ms 37496 KB Output is correct
66 Correct 481 ms 38904 KB Output is correct
67 Correct 476 ms 37496 KB Output is correct
68 Correct 496 ms 39216 KB Output is correct
69 Correct 477 ms 39800 KB Output is correct
70 Correct 473 ms 37880 KB Output is correct
71 Correct 460 ms 38956 KB Output is correct
72 Correct 476 ms 41508 KB Output is correct
73 Correct 428 ms 41336 KB Output is correct
74 Correct 436 ms 46500 KB Output is correct