oj.uz

Submission #102079

# Submission time Handle Problem Language Result Execution time Memory
102079 2019-03-22T07:06:58 Z ainta Designated Cities (JOI19_designated_cities) C++17
100 / 100
 836 ms 48708 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 201000
#define SZ 262144
#define pii pair<int,int>
#define X first
#define Y second
using namespace std;
vector<int>E[N_];
int n, chk[N_], cnt;
long long S[N_], Far[N_], Res[N_];
struct Edge {
	int e, l;
}Ed[N_*2];
void Add_Edge(int a, int b, int c) {
	E[a].push_back(cnt);
	Ed[cnt++] = { b,c };
}
void DFS1(int a, int pp) {
	for (auto &t : E[a]) {
		int x = Ed[t].e, l = Ed[t].l;
		if (x == pp)continue;
		DFS1(x, a);
		Far[a] = max(Far[a], Far[x] + l);
		S[a] += S[x] + l;
	}
}
void DFS2(int a, int pp, long long f) {
	int pv1 = -1, pv2 = -1;
	long long f1 = 0, f2 = 0;
	Far[a] = max(Far[a], f);
	for (auto &t : E[a]) {
		int x = Ed[t].e, l = Ed[t].l;
		if (x == pp)continue;
		S[x] = S[a] - l + Ed[t ^ 1].l;
		if (f1 <= Far[x] + l) {
			pv2 = pv1, f2 = f1;
			pv1 = x, f1 = Far[x] + l;
		}
		else if (f2 <= Far[x] + l) {
			pv2 = x, f2 = Far[x] + l;
		}
	}
	for (auto &t : E[a]) {
		int x = Ed[t].e, l = Ed[t].l;
		if (x == pp)continue;
		if (x == pv1) {
			DFS2(x, a, Ed[t ^ 1].l + max(f2,f));
		}
		else {
			DFS2(x, a, Ed[t ^ 1].l + max(f1,f));
		}
	}
}
int Num[N_], End[N_], ReNum[N_], par[N_], pL[N_];
long long DD[N_];
struct Tree {
	long long Mx[SZ + SZ], K[SZ + SZ];
	void UDT(int nd) {
		Mx[nd] = max(Mx[nd * 2], Mx[nd * 2 + 1]);
	}
	void init(int nd, int b, int e) {
		K[nd] = 0;
		if (b == e) {
			Mx[nd] = DD[ReNum[b]];
			return;
		}
		int m = (b + e) >> 1;
		init(nd * 2, b, m);
		init(nd * 2 + 1, m + 1, e);
		UDT(nd);
	}
	void Add2(int nd, long long x) {
		Mx[nd] += x;
		K[nd] += x;
	}
	void Spread(int nd) {
		Add2(nd * 2, K[nd]);
		Add2(nd * 2 + 1, K[nd]);
		K[nd] = 0;
	}
	void Add(int nd, int b, int e, int s, int l, long long x) {
		if (s > l)return;
		if (b == s && e == l) {
			Add2(nd, x);
			return;
		}
		int m = (b + e) >> 1;
		Spread(nd);
		if (s <= m)Add(nd * 2, b, m, s, min(m, l), x);
		if (l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, x);
		UDT(nd);
	}
	int Find(int nd, int b, int e) {
		if (Mx[nd] == 0)return 0;
		if (b == e)return ReNum[b];
		int m = (b + e) >> 1;
		Spread(nd);
		if (Mx[nd * 2] == Mx[nd])return Find(nd * 2, b, m);
		return Find(nd * 2 + 1, m + 1, e);
	}
}TT;
void DFS3(int a, int pp, long long d) {
	Num[a] = ++cnt;
	ReNum[cnt] = a;
	DD[a] = d;
	par[a] = pp;
	for (auto &t : E[a]) {
		int x = Ed[t].e, l = Ed[t].l;
		if (x == pp)continue;
		pL[x] = l;
		DFS3(x, a, d+l);
	}
	End[a] = cnt;
}
int main() {
	//freopen("input.txt", "r", stdin);
	int i, a, b, c, d;
	scanf("%d", &n);
	for (i = 1; i < n; i++) {
		scanf("%d%d%d%d", &a, &b, &c, &d);
		Add_Edge(a, b, c);
		Add_Edge(b, a, d);
	}
	DFS1(1, 0);
	DFS2(1, 0, 0);
	for (i = 1; i <= n; i++)Res[i] = 1e18;
	for (i = 1; i <= n; i++)Res[1] = min(Res[1], S[i]);
	int pv = -1;
	for (i = 1; i <= n; i++) {
		if (Res[2] > S[i] - Far[i]) {
			Res[2] = S[i] - Far[i];
			pv = i;
		}
	}

	int root = pv;
	cnt = 0;
	DFS3(root, 0, 0);
	TT.init(1, 1, n);
	for (i = 1; i <= n; i++)chk[i] = 0;
	chk[root] = 1;
	long long ss = S[root];
	for (i = 2; i <= n; i++) {
		ss -= TT.Mx[1];
		Res[i] = min(Res[i], ss);
		int a = TT.Find(1, 1, n);
		if (!a) continue;
		while (!chk[a]) {
			TT.Add(1, 1, n, Num[a], End[a], -pL[a]);
			chk[a] = 1;
			a = par[a];
		}
	}
	int Q;
	scanf("%d", &Q);
	while (Q--) {
		scanf("%d", &a);
		printf("%lld\n", Res[a]);
	}
}

Compilation message

designated_cities.cpp: In function 'void DFS2(int, int, long long int)':
designated_cities.cpp:46:20: warning: unused variable 'l' [-Wunused-variable]
   int x = Ed[t].e, l = Ed[t].l;
                    ^
designated_cities.cpp:30:16: warning: variable 'pv2' set but not used [-Wunused-but-set-variable]
  int pv1 = -1, pv2 = -1;
                ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 727 ms 33784 KB Output is correct
3 Correct 784 ms 46584 KB Output is correct
4 Correct 680 ms 33788 KB Output is correct
5 Correct 676 ms 33780 KB Output is correct
6 Correct 700 ms 35448 KB Output is correct
7 Correct 637 ms 34160 KB Output is correct
8 Correct 818 ms 46792 KB Output is correct
9 Correct 523 ms 34536 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 709 ms 33840 KB Output is correct
3 Correct 766 ms 48664 KB Output is correct
4 Correct 680 ms 33792 KB Output is correct
5 Correct 685 ms 34072 KB Output is correct
6 Correct 694 ms 35896 KB Output is correct
7 Correct 510 ms 34664 KB Output is correct
8 Correct 724 ms 41848 KB Output is correct
9 Correct 507 ms 34476 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5092 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
13 Correct 12 ms 5376 KB Output is correct
14 Correct 9 ms 5504 KB Output is correct
15 Correct 9 ms 5376 KB Output is correct
16 Correct 10 ms 5376 KB Output is correct
17 Correct 10 ms 5376 KB Output is correct
18 Correct 10 ms 5376 KB Output is correct
19 Correct 12 ms 5504 KB Output is correct
20 Correct 11 ms 5376 KB Output is correct
21 Correct 11 ms 5376 KB Output is correct
22 Correct 10 ms 5376 KB Output is correct
23 Correct 10 ms 5376 KB Output is correct
24 Correct 12 ms 5376 KB Output is correct
25 Correct 12 ms 5504 KB Output is correct
26 Correct 10 ms 5376 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 727 ms 33784 KB Output is correct
3 Correct 784 ms 46584 KB Output is correct
4 Correct 680 ms 33788 KB Output is correct
5 Correct 676 ms 33780 KB Output is correct
6 Correct 700 ms 35448 KB Output is correct
7 Correct 637 ms 34160 KB Output is correct
8 Correct 818 ms 46792 KB Output is correct
9 Correct 523 ms 34536 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 709 ms 33840 KB Output is correct
12 Correct 766 ms 48664 KB Output is correct
13 Correct 680 ms 33792 KB Output is correct
14 Correct 685 ms 34072 KB Output is correct
15 Correct 694 ms 35896 KB Output is correct
16 Correct 510 ms 34664 KB Output is correct
17 Correct 724 ms 41848 KB Output is correct
18 Correct 507 ms 34476 KB Output is correct
19 Correct 7 ms 5120 KB Output is correct
20 Correct 689 ms 33816 KB Output is correct
21 Correct 787 ms 48708 KB Output is correct
22 Correct 713 ms 33724 KB Output is correct
23 Correct 687 ms 33756 KB Output is correct
24 Correct 616 ms 33768 KB Output is correct
25 Correct 690 ms 33784 KB Output is correct
26 Correct 680 ms 33888 KB Output is correct
27 Correct 755 ms 33984 KB Output is correct
28 Correct 679 ms 35576 KB Output is correct
29 Correct 747 ms 34040 KB Output is correct
30 Correct 725 ms 33900 KB Output is correct
31 Correct 655 ms 34124 KB Output is correct
32 Correct 748 ms 42240 KB Output is correct
33 Correct 656 ms 34496 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5092 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
13 Correct 727 ms 33784 KB Output is correct
14 Correct 784 ms 46584 KB Output is correct
15 Correct 680 ms 33788 KB Output is correct
16 Correct 676 ms 33780 KB Output is correct
17 Correct 700 ms 35448 KB Output is correct
18 Correct 637 ms 34160 KB Output is correct
19 Correct 818 ms 46792 KB Output is correct
20 Correct 523 ms 34536 KB Output is correct
21 Correct 7 ms 5120 KB Output is correct
22 Correct 709 ms 33840 KB Output is correct
23 Correct 766 ms 48664 KB Output is correct
24 Correct 680 ms 33792 KB Output is correct
25 Correct 685 ms 34072 KB Output is correct
26 Correct 694 ms 35896 KB Output is correct
27 Correct 510 ms 34664 KB Output is correct
28 Correct 724 ms 41848 KB Output is correct
29 Correct 507 ms 34476 KB Output is correct
30 Correct 6 ms 5120 KB Output is correct
31 Correct 12 ms 5376 KB Output is correct
32 Correct 9 ms 5504 KB Output is correct
33 Correct 9 ms 5376 KB Output is correct
34 Correct 10 ms 5376 KB Output is correct
35 Correct 10 ms 5376 KB Output is correct
36 Correct 10 ms 5376 KB Output is correct
37 Correct 12 ms 5504 KB Output is correct
38 Correct 11 ms 5376 KB Output is correct
39 Correct 11 ms 5376 KB Output is correct
40 Correct 10 ms 5376 KB Output is correct
41 Correct 10 ms 5376 KB Output is correct
42 Correct 12 ms 5376 KB Output is correct
43 Correct 12 ms 5504 KB Output is correct
44 Correct 10 ms 5376 KB Output is correct
45 Correct 7 ms 5120 KB Output is correct
46 Correct 689 ms 33816 KB Output is correct
47 Correct 787 ms 48708 KB Output is correct
48 Correct 713 ms 33724 KB Output is correct
49 Correct 687 ms 33756 KB Output is correct
50 Correct 616 ms 33768 KB Output is correct
51 Correct 690 ms 33784 KB Output is correct
52 Correct 680 ms 33888 KB Output is correct
53 Correct 755 ms 33984 KB Output is correct
54 Correct 679 ms 35576 KB Output is correct
55 Correct 747 ms 34040 KB Output is correct
56 Correct 725 ms 33900 KB Output is correct
57 Correct 655 ms 34124 KB Output is correct
58 Correct 748 ms 42240 KB Output is correct
59 Correct 656 ms 34496 KB Output is correct
60 Correct 7 ms 5120 KB Output is correct
61 Correct 752 ms 35116 KB Output is correct
62 Correct 816 ms 46912 KB Output is correct
63 Correct 729 ms 35196 KB Output is correct
64 Correct 836 ms 35076 KB Output is correct
65 Correct 728 ms 34940 KB Output is correct
66 Correct 807 ms 35068 KB Output is correct
67 Correct 689 ms 34952 KB Output is correct
68 Correct 738 ms 35256 KB Output is correct
69 Correct 767 ms 36784 KB Output is correct
70 Correct 704 ms 35260 KB Output is correct
71 Correct 711 ms 35308 KB Output is correct
72 Correct 666 ms 36144 KB Output is correct
73 Correct 818 ms 42736 KB Output is correct
74 Correct 616 ms 37376 KB Output is correct