oj.uz

Submission #204196

# Submission time Handle Problem Language Result Execution time Memory
204196 2020-02-25T07:35:41 Z cheetose Designated Cities (JOI19_designated_cities) C++11
16 / 100
 635 ms 69564 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 tuple<ll, ll, ll, ll> LLLL;
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];
VLLL 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<LLLL> Q;
LLL dfs4(int N,int p=-1)
{
	for(auto &P:v[N])
	{
		if(P.y==p)continue;
		LLL L=dfs4(P.y,N);
		vv[N].pb(LLL(P.y,P.c+get<1>(L),get<2>(L)));
	}
	sort(ALL(vv[N]),[&](LLL p1,LLL p2){
		return get<1>(p1)>get<1>(p2);
	});
	sz[N]=vv[N].size();
	fup(i,0,sz[N]-1,1)Q.push(LLLL(get<1>(vv[N][i]),N,-i,get<2>(vv[N][i])));
	if(vv[N].empty())return LLL(0,0,N);
	return vv[N][0];
}
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);
	now=get<0>(mx);
	ans[2]=now;
	int cc=2;
	while(!Q.empty())
	{
		ll x,N,i,ww;
		tie(x,N,i,ww)=Q.top();
		i*=-1;
		Q.pop();
		if(i<pt[N])continue;
		if(ww==T1 || ww==T2)
		{
			while(pt[N]<sz[N])
			{
				pt[N]++;
				N=get<0>(vv[N][pt[N]-1]);
			}
			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:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
designated_cities.cpp:113: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:117:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
designated_cities.cpp:127: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:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
designated_cities.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
designated_cities.cpp:138:15: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ll now=dfs1(R);
               ^

Subtask #1
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 Incorrect 11 ms 9720 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 587 ms 49240 KB Output is correct
3 Correct 614 ms 60392 KB Output is correct
4 Correct 545 ms 45652 KB Output is correct
5 Correct 560 ms 45464 KB Output is correct
6 Correct 620 ms 49204 KB Output is correct
7 Correct 460 ms 43936 KB Output is correct
8 Correct 634 ms 69564 KB Output is correct
9 Correct 317 ms 41688 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct
2 Correct 595 ms 49240 KB Output is correct
3 Correct 618 ms 58448 KB Output is correct
4 Correct 556 ms 45140 KB Output is correct
5 Correct 557 ms 45064 KB Output is correct
6 Correct 603 ms 48592 KB Output is correct
7 Correct 348 ms 47500 KB Output is correct
8 Correct 635 ms 65616 KB Output is correct
9 Correct 309 ms 41048 KB Output is correct

Subtask #4
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 Incorrect 11 ms 9720 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 587 ms 49240 KB Output is correct
3 Correct 614 ms 60392 KB Output is correct
4 Correct 545 ms 45652 KB Output is correct
5 Correct 560 ms 45464 KB Output is correct
6 Correct 620 ms 49204 KB Output is correct
7 Correct 460 ms 43936 KB Output is correct
8 Correct 634 ms 69564 KB Output is correct
9 Correct 317 ms 41688 KB Output is correct
10 Correct 11 ms 9848 KB Output is correct
11 Correct 595 ms 49240 KB Output is correct
12 Correct 618 ms 58448 KB Output is correct
13 Correct 556 ms 45140 KB Output is correct
14 Correct 557 ms 45064 KB Output is correct
15 Correct 603 ms 48592 KB Output is correct
16 Correct 348 ms 47500 KB Output is correct
17 Correct 635 ms 65616 KB Output is correct
18 Correct 309 ms 41048 KB Output is correct
19 Correct 11 ms 9720 KB Output is correct
20 Correct 597 ms 45344 KB Output is correct
21 Correct 619 ms 65364 KB Output is correct
22 Incorrect 542 ms 48976 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
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 Incorrect 11 ms 9720 KB Output isn't correct
5 Halted 0 ms 0 KB -