oj.uz

Submission #122886

# Submission time Handle Problem Language Result Execution time Memory
122886 2019-06-29T13:00:21 Z MvC Designated Cities (JOI19_designated_cities) C++11
39 / 100
 461 ms 94540 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "rail.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const int mod=1e9+7;
using namespace std;
int a[nmax],b[nmax],i,x,q,m,sz[nmax],n;
ll c[nmax],d[nmax],tot,cur[nmax],ans,tmp[nmax];
vector<ll>f[nmax],g[nmax];
vector<int>v[nmax];
int oth(int i,int x)
{
	return a[i]^b[i]^x;
}
ll cst(int i,int x,int y)
{
	if(a[i]==x)return c[i];
	return d[i];
}
void dfs(int x,int p,ll l)
{
	cur[x]=l;
	for(int i=0;i<v[x].size();i++)
	{
		int y=oth(v[x][i],x);
		ll z=cst(v[x][i],y,x)-cst(v[x][i],x,y);
		if(y==p)continue;
		dfs(y,x,l+z);
	}
	sz[x]=1;
	for(int i=0;i<v[x].size();i++)
	{
		int y=oth(v[x][i],x);
		ll z=cst(v[x][i],x,y);
		if(y==p)continue;
		tot+=z;
		for(int j=1;j<=min(sz[x],m);j++)
		{
			for(int t=1;t<=min(sz[y],m);t++)
			{
				f[x][j+t]=max(f[x][j+t],g[x][j]+g[y][t]+z);
			}
		}
		for(int j=0;j<=min(sz[x]+sz[y],m);j++)tmp[j]=0;
		for(int j=0;j<=min(sz[x],m);j++)
		{
			for(int t=1;t<=min(sz[y],m);t++)
			{
				tmp[j+t]=max(tmp[j+t],g[x][j]+g[y][t]+z);
			}
		}
		sz[x]+=sz[y];
		for(int j=0;j<=min(sz[x],m);j++)
		{
			g[x][j]=max(g[x][j],tmp[j]);
		}
	}
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<n;i++)
	{
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		v[a[i]].pb(i);
		v[b[i]].pb(i);
	}
	if(n>2000)m=2;
	else m=n;
	for(i=1;i<=n;i++)
	{
		f[i].assign(m+2,0);
		g[i].assign(m+2,0);
	}
	dfs(1,0,0);
	cin>>q;
	while(q--)
	{
		cin>>x;
		ans=llinf;
		for(i=1;i<=n;i++)ans=min(ans,tot-f[i][min(sz[i],x)]+cur[i]);
		ans=max(ans,0LL);
		cout<<ans<<endl;
	}
    return 0;
}

Compilation message

designated_cities.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
designated_cities.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
designated_cities.cpp: In function 'void dfs(int, int, ll)':
designated_cities.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++)
              ~^~~~~~~~~~~~
designated_cities.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++)
              ~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14456 KB Output is correct
2 Correct 15 ms 14460 KB Output is correct
3 Correct 16 ms 14456 KB Output is correct
4 Correct 16 ms 14480 KB Output is correct
5 Correct 16 ms 14516 KB Output is correct
6 Correct 19 ms 14456 KB Output is correct
7 Correct 16 ms 14456 KB Output is correct
8 Correct 16 ms 14456 KB Output is correct
9 Correct 16 ms 14456 KB Output is correct
10 Correct 19 ms 14484 KB Output is correct
11 Correct 16 ms 14456 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14456 KB Output is correct
2 Correct 351 ms 46712 KB Output is correct
3 Correct 461 ms 69648 KB Output is correct
4 Correct 412 ms 46912 KB Output is correct
5 Correct 337 ms 46900 KB Output is correct
6 Correct 416 ms 49908 KB Output is correct
7 Correct 307 ms 47216 KB Output is correct
8 Correct 416 ms 70300 KB Output is correct
9 Correct 272 ms 47464 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14456 KB Output is correct
2 Correct 360 ms 46832 KB Output is correct
3 Correct 412 ms 73464 KB Output is correct
4 Correct 346 ms 46916 KB Output is correct
5 Correct 344 ms 47008 KB Output is correct
6 Correct 352 ms 50360 KB Output is correct
7 Correct 275 ms 47464 KB Output is correct
8 Correct 383 ms 61180 KB Output is correct
9 Correct 266 ms 47592 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14456 KB Output is correct
2 Correct 15 ms 14460 KB Output is correct
3 Correct 16 ms 14456 KB Output is correct
4 Correct 16 ms 14480 KB Output is correct
5 Correct 16 ms 14516 KB Output is correct
6 Correct 19 ms 14456 KB Output is correct
7 Correct 16 ms 14456 KB Output is correct
8 Correct 16 ms 14456 KB Output is correct
9 Correct 16 ms 14456 KB Output is correct
10 Correct 19 ms 14484 KB Output is correct
11 Correct 16 ms 14456 KB Output is correct
12 Correct 15 ms 14456 KB Output is correct
13 Correct 125 ms 77504 KB Output is correct
14 Correct 131 ms 77572 KB Output is correct
15 Correct 124 ms 77432 KB Output is correct
16 Correct 125 ms 77432 KB Output is correct
17 Correct 128 ms 77508 KB Output is correct
18 Correct 125 ms 77440 KB Output is correct
19 Correct 126 ms 77432 KB Output is correct
20 Correct 129 ms 77496 KB Output is correct
21 Correct 125 ms 77432 KB Output is correct
22 Correct 127 ms 77432 KB Output is correct
23 Correct 127 ms 77560 KB Output is correct
24 Correct 142 ms 77524 KB Output is correct
25 Correct 156 ms 77820 KB Output is correct
26 Correct 140 ms 77436 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14456 KB Output is correct
2 Correct 351 ms 46712 KB Output is correct
3 Correct 461 ms 69648 KB Output is correct
4 Correct 412 ms 46912 KB Output is correct
5 Correct 337 ms 46900 KB Output is correct
6 Correct 416 ms 49908 KB Output is correct
7 Correct 307 ms 47216 KB Output is correct
8 Correct 416 ms 70300 KB Output is correct
9 Correct 272 ms 47464 KB Output is correct
10 Correct 16 ms 14456 KB Output is correct
11 Correct 360 ms 46832 KB Output is correct
12 Correct 412 ms 73464 KB Output is correct
13 Correct 346 ms 46916 KB Output is correct
14 Correct 344 ms 47008 KB Output is correct
15 Correct 352 ms 50360 KB Output is correct
16 Correct 275 ms 47464 KB Output is correct
17 Correct 383 ms 61180 KB Output is correct
18 Correct 266 ms 47592 KB Output is correct
19 Correct 15 ms 14456 KB Output is correct
20 Runtime error 394 ms 94540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14456 KB Output is correct
2 Correct 15 ms 14460 KB Output is correct
3 Correct 16 ms 14456 KB Output is correct
4 Correct 16 ms 14480 KB Output is correct
5 Correct 16 ms 14516 KB Output is correct
6 Correct 19 ms 14456 KB Output is correct
7 Correct 16 ms 14456 KB Output is correct
8 Correct 16 ms 14456 KB Output is correct
9 Correct 16 ms 14456 KB Output is correct
10 Correct 19 ms 14484 KB Output is correct
11 Correct 16 ms 14456 KB Output is correct
12 Correct 16 ms 14456 KB Output is correct
13 Correct 351 ms 46712 KB Output is correct
14 Correct 461 ms 69648 KB Output is correct
15 Correct 412 ms 46912 KB Output is correct
16 Correct 337 ms 46900 KB Output is correct
17 Correct 416 ms 49908 KB Output is correct
18 Correct 307 ms 47216 KB Output is correct
19 Correct 416 ms 70300 KB Output is correct
20 Correct 272 ms 47464 KB Output is correct
21 Correct 16 ms 14456 KB Output is correct
22 Correct 360 ms 46832 KB Output is correct
23 Correct 412 ms 73464 KB Output is correct
24 Correct 346 ms 46916 KB Output is correct
25 Correct 344 ms 47008 KB Output is correct
26 Correct 352 ms 50360 KB Output is correct
27 Correct 275 ms 47464 KB Output is correct
28 Correct 383 ms 61180 KB Output is correct
29 Correct 266 ms 47592 KB Output is correct
30 Correct 15 ms 14456 KB Output is correct
31 Correct 125 ms 77504 KB Output is correct
32 Correct 131 ms 77572 KB Output is correct
33 Correct 124 ms 77432 KB Output is correct
34 Correct 125 ms 77432 KB Output is correct
35 Correct 128 ms 77508 KB Output is correct
36 Correct 125 ms 77440 KB Output is correct
37 Correct 126 ms 77432 KB Output is correct
38 Correct 129 ms 77496 KB Output is correct
39 Correct 125 ms 77432 KB Output is correct
40 Correct 127 ms 77432 KB Output is correct
41 Correct 127 ms 77560 KB Output is correct
42 Correct 142 ms 77524 KB Output is correct
43 Correct 156 ms 77820 KB Output is correct
44 Correct 140 ms 77436 KB Output is correct
45 Correct 15 ms 14456 KB Output is correct
46 Runtime error 394 ms 94540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Halted 0 ms 0 KB -