oj.uz

Submission #204216

# Submission time Handle Problem Language Result Execution time Memory
204216 2020-02-25T08:19:16 Z cheetose Designated Cities (JOI19_designated_cities) C++11
100 / 100
 685 ms 57708 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<ld> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const int MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };
int ddx[] = { -1,-2,1,-2,2,-1,2,1 }, ddy[] = { -2,-1,-2,1,-1,2,1,2 };

struct A {
	int y;
	ll c, d;
};
vector<A> v[200001];
VPll vv[200001];
int pt[200001], sz[200001];
ll sum, ans[200001];
ll Q1[200001], q1;
LLL Q2[200001];
ll dfs1(int N, int p = -1)
{
	ll res = 0;
	for (auto &P : v[N])
	{
		if (P.y == p)continue;
		res += P.d + dfs1(P.y, N);
	}
	return res;
}
void dfs2(int N, ll now, int p = -1)
{
	q1 = max(q1, now);
	Q1[N] = now;
	for (auto &P : v[N])
	{
		if (P.y == p)continue;
		dfs2(P.y, now + P.c - P.d, N);
	}
}
Pll dfs3(int N, int p = -1)
{
	VPll V;
	for (auto &P : v[N])
	{
		if (P.y == p)continue;
		Pll pp = dfs3(P.y, N);
		V.pb(mp(P.c + pp.X, pp.Y));
	}
	if (V.empty())return mp(0, N);
	sort(V.rbegin(), V.rend());
	if (V.size()>1)Q2[N] = LLL(Q1[N] + V[0].X + V[1].X, V[0].Y, V[1].Y);
	return V[0];
}
ll T1, T2;
priority_queue<LLL> Q;
int ind[200001], parent[200001];
void dfs4(int N, int p = -1)
{
	parent[N] = p;
	for (auto &P : v[N])
	{
		if (P.y == p)continue;
		dfs4(P.y, N);
	}
}
Pll dfs5(int N)
{
	for (auto &P : v[N])
	{
		vv[N].pb(mp(P.y, P.c + dfs5(P.y).Y));
	}
	sort(ALL(vv[N]), [&](Pll p1, Pll p2) {
		return p1.Y>p2.Y;
	});
	sz[N] = vv[N].size();
	fup(i, 0, sz[N] - 1, 1)Q.push(LLL(vv[N][i].Y, N, -i));
	if (vv[N].empty())return mp(0, 0);
	return vv[N][0];
}
void rem(int T, int R)
{
	int NOW = T;
	while (NOW != R)
	{
		int next = parent[NOW];
		for (auto &P : v[next])
		{
			if (P.y == NOW)
			{
				swap(P, v[next].back());
				break;
			}
		}
		v[next].pop_back();
		NOW = next;
	}
}
int main() {
	int n, R;
	scanf("%d", &n);
	if (n == 2)
	{
		int a, b, c, d, q;
		scanf("%d%d%d%d%d", &a, &b, &c, &d, &q);
		while (q--)
		{
			int x;
			scanf("%d", &x);
			if (x == 1)printf("%d\n", min(c, d));
			else puts("0");
		}
		return 0;
	}
	fup(i, 1, n - 1, 1)
	{
		int x, y;
		ll c, d;
		scanf("%d%d%lld%lld", &x, &y, &c, &d);
		sum += c + d;
		v[x].pb({ y,c,d });
		v[y].pb({ x,d,c });
	}
	int leafcnt = 0;
	fup(i, 1, n, 1)
	{
		if (v[i].size()>1)R = i;
		else leafcnt++;
	}
	ll now = dfs1(R);
	dfs2(R, now);
	int q;
	scanf("%d", &q);
	ans[1] = q1;
	dfs3(R);
	R = -1;
	LLL mx = LLL(-1, -1, -1);
	fup(i, 1, n, 1)
		if (Q2[i]>mx)R = i, mx = Q2[i];
	T1 = get<1>(mx), T2 = get<2>(mx);
	dfs4(R);
	fup(i, 1, n, 1)
	{
		if (i == R)continue;
		for (auto &P : v[i])
		{
			if (P.y == parent[i])
			{
				swap(P, v[i].back());
				break;
			}
		}
		v[i].pop_back();
	}
	rem(T1, R); rem(T2, R);
	fup(i, 1, n, 1)
		for (auto &P : v[i])ind[P.y]++;
	fup(i, 1, n, 1)if (!ind[i])dfs5(i);
	now = get<0>(mx);
	ans[2] = now;
	int cc = 2;
	while (!Q.empty())
	{
		ll x, N, i;
		tie(x, N, i) = Q.top();
		i *= -1;
		Q.pop();
		if (i<pt[N])continue;
		cc++, now += x;
		if (cc >= 2)ans[cc] = now;
		while (pt[N]<sz[N])
		{
			pt[N]++;
			N = get<0>(vv[N][pt[N] - 1]);
		}
	}
	while (q--)
	{
		int x;
		scanf("%d", &x);
		if (x >= leafcnt)puts("0");
		else printf("%lld\n", sum - ans[x]);
	}
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d%d", &a, &b, &c, &d, &q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:142:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~
designated_cities.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld%lld", &x, &y, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:166:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:213:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
designated_cities.cpp:163:17: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ll now = dfs1(R);
                 ^

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 640 ms 44516 KB Output is correct
3 Correct 532 ms 41976 KB Output is correct
4 Correct 610 ms 44716 KB Output is correct
5 Correct 611 ms 44328 KB Output is correct
6 Correct 650 ms 46044 KB Output is correct
7 Correct 482 ms 45592 KB Output is correct
8 Correct 532 ms 51316 KB Output is correct
9 Correct 308 ms 43132 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 635 ms 44596 KB Output is correct
3 Correct 505 ms 39928 KB Output is correct
4 Correct 584 ms 43800 KB Output is correct
5 Correct 582 ms 43944 KB Output is correct
6 Correct 612 ms 44728 KB Output is correct
7 Correct 336 ms 45068 KB Output is correct
8 Correct 581 ms 51704 KB Output is correct
9 Correct 303 ms 42044 KB Output is correct

Subtask #4
17.0 / 17.0

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

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 640 ms 44516 KB Output is correct
3 Correct 532 ms 41976 KB Output is correct
4 Correct 610 ms 44716 KB Output is correct
5 Correct 611 ms 44328 KB Output is correct
6 Correct 650 ms 46044 KB Output is correct
7 Correct 482 ms 45592 KB Output is correct
8 Correct 532 ms 51316 KB Output is correct
9 Correct 308 ms 43132 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 635 ms 44596 KB Output is correct
12 Correct 505 ms 39928 KB Output is correct
13 Correct 584 ms 43800 KB Output is correct
14 Correct 582 ms 43944 KB Output is correct
15 Correct 612 ms 44728 KB Output is correct
16 Correct 336 ms 45068 KB Output is correct
17 Correct 581 ms 51704 KB Output is correct
18 Correct 303 ms 42044 KB Output is correct
19 Correct 11 ms 9720 KB Output is correct
20 Correct 614 ms 43920 KB Output is correct
21 Correct 521 ms 41692 KB Output is correct
22 Correct 580 ms 44696 KB Output is correct
23 Correct 622 ms 49276 KB Output is correct
24 Correct 619 ms 48152 KB Output is correct
25 Correct 646 ms 49328 KB Output is correct
26 Correct 637 ms 48112 KB Output is correct
27 Correct 590 ms 48932 KB Output is correct
28 Correct 614 ms 50552 KB Output is correct
29 Correct 621 ms 49304 KB Output is correct
30 Correct 553 ms 48244 KB Output is correct
31 Correct 429 ms 50324 KB Output is correct
32 Correct 564 ms 55428 KB Output is correct
33 Correct 312 ms 47728 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 12 ms 9720 KB Output is correct
5 Correct 11 ms 9720 KB Output is correct
6 Correct 12 ms 9720 KB Output is correct
7 Correct 12 ms 9720 KB Output is correct
8 Correct 11 ms 9720 KB Output is correct
9 Correct 11 ms 9720 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 11 ms 9720 KB Output is correct
12 Correct 11 ms 9720 KB Output is correct
13 Correct 640 ms 44516 KB Output is correct
14 Correct 532 ms 41976 KB Output is correct
15 Correct 610 ms 44716 KB Output is correct
16 Correct 611 ms 44328 KB Output is correct
17 Correct 650 ms 46044 KB Output is correct
18 Correct 482 ms 45592 KB Output is correct
19 Correct 532 ms 51316 KB Output is correct
20 Correct 308 ms 43132 KB Output is correct
21 Correct 11 ms 9720 KB Output is correct
22 Correct 635 ms 44596 KB Output is correct
23 Correct 505 ms 39928 KB Output is correct
24 Correct 584 ms 43800 KB Output is correct
25 Correct 582 ms 43944 KB Output is correct
26 Correct 612 ms 44728 KB Output is correct
27 Correct 336 ms 45068 KB Output is correct
28 Correct 581 ms 51704 KB Output is correct
29 Correct 303 ms 42044 KB Output is correct
30 Correct 11 ms 9720 KB Output is correct
31 Correct 16 ms 10104 KB Output is correct
32 Correct 14 ms 10232 KB Output is correct
33 Correct 14 ms 10104 KB Output is correct
34 Correct 14 ms 10104 KB Output is correct
35 Correct 14 ms 10104 KB Output is correct
36 Correct 14 ms 10224 KB Output is correct
37 Correct 14 ms 10104 KB Output is correct
38 Correct 14 ms 10108 KB Output is correct
39 Correct 14 ms 10232 KB Output is correct
40 Correct 14 ms 10104 KB Output is correct
41 Correct 15 ms 10232 KB Output is correct
42 Correct 14 ms 10232 KB Output is correct
43 Correct 14 ms 10232 KB Output is correct
44 Correct 14 ms 10104 KB Output is correct
45 Correct 11 ms 9720 KB Output is correct
46 Correct 614 ms 43920 KB Output is correct
47 Correct 521 ms 41692 KB Output is correct
48 Correct 580 ms 44696 KB Output is correct
49 Correct 622 ms 49276 KB Output is correct
50 Correct 619 ms 48152 KB Output is correct
51 Correct 646 ms 49328 KB Output is correct
52 Correct 637 ms 48112 KB Output is correct
53 Correct 590 ms 48932 KB Output is correct
54 Correct 614 ms 50552 KB Output is correct
55 Correct 621 ms 49304 KB Output is correct
56 Correct 553 ms 48244 KB Output is correct
57 Correct 429 ms 50324 KB Output is correct
58 Correct 564 ms 55428 KB Output is correct
59 Correct 312 ms 47728 KB Output is correct
60 Correct 10 ms 9720 KB Output is correct
61 Correct 674 ms 50840 KB Output is correct
62 Correct 550 ms 47780 KB Output is correct
63 Correct 626 ms 50584 KB Output is correct
64 Correct 669 ms 50456 KB Output is correct
65 Correct 655 ms 50220 KB Output is correct
66 Correct 666 ms 50328 KB Output is correct
67 Correct 670 ms 50500 KB Output is correct
68 Correct 647 ms 50120 KB Output is correct
69 Correct 685 ms 51348 KB Output is correct
70 Correct 675 ms 50528 KB Output is correct
71 Correct 603 ms 51004 KB Output is correct
72 Correct 513 ms 52244 KB Output is correct
73 Correct 600 ms 57708 KB Output is correct
74 Correct 367 ms 50164 KB Output is correct