oj.uz

Submission #122885

# Submission time Handle Problem Language Result Execution time Memory
122885 2019-06-29T12:59:33 Z MvC Designated Cities (JOI19_designated_cities) C++11
39 / 100
 536 ms 195704 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=5;
	else m=2003;
	for(i=1;i<=n;i++)
	{
		f[i].assign(m+15,0);
		g[i].assign(m+15,0);
	}
	dfs(1,-1,0);
	//cout<<tot<<endl;
	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 15 ms 14456 KB Output is correct
2 Correct 15 ms 14968 KB Output is correct
3 Correct 16 ms 14968 KB Output is correct
4 Correct 16 ms 14968 KB Output is correct
5 Correct 18 ms 14968 KB Output is correct
6 Correct 19 ms 14968 KB Output is correct
7 Correct 16 ms 14968 KB Output is correct
8 Correct 16 ms 14968 KB Output is correct
9 Correct 16 ms 14992 KB Output is correct
10 Correct 16 ms 14968 KB Output is correct
11 Correct 16 ms 14968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14584 KB Output is correct
2 Correct 447 ms 96784 KB Output is correct
3 Correct 508 ms 119652 KB Output is correct
4 Correct 439 ms 96888 KB Output is correct
5 Correct 423 ms 97040 KB Output is correct
6 Correct 467 ms 99960 KB Output is correct
7 Correct 392 ms 97288 KB Output is correct
8 Correct 521 ms 120312 KB Output is correct
9 Correct 337 ms 97600 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 460 ms 96968 KB Output is correct
3 Correct 536 ms 123516 KB Output is correct
4 Correct 446 ms 96888 KB Output is correct
5 Correct 408 ms 97012 KB Output is correct
6 Correct 472 ms 100600 KB Output is correct
7 Correct 361 ms 97648 KB Output is correct
8 Correct 508 ms 111096 KB Output is correct
9 Correct 338 ms 97512 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 15 ms 14968 KB Output is correct
3 Correct 16 ms 14968 KB Output is correct
4 Correct 16 ms 14968 KB Output is correct
5 Correct 18 ms 14968 KB Output is correct
6 Correct 19 ms 14968 KB Output is correct
7 Correct 16 ms 14968 KB Output is correct
8 Correct 16 ms 14968 KB Output is correct
9 Correct 16 ms 14992 KB Output is correct
10 Correct 16 ms 14968 KB Output is correct
11 Correct 16 ms 14968 KB Output is correct
12 Correct 15 ms 14584 KB Output is correct
13 Correct 124 ms 77944 KB Output is correct
14 Correct 136 ms 78044 KB Output is correct
15 Correct 128 ms 78092 KB Output is correct
16 Correct 126 ms 77944 KB Output is correct
17 Correct 126 ms 77944 KB Output is correct
18 Correct 144 ms 77948 KB Output is correct
19 Correct 137 ms 77972 KB Output is correct
20 Correct 143 ms 77900 KB Output is correct
21 Correct 145 ms 78000 KB Output is correct
22 Correct 130 ms 77992 KB Output is correct
23 Correct 133 ms 78012 KB Output is correct
24 Correct 139 ms 77944 KB Output is correct
25 Correct 141 ms 78172 KB Output is correct
26 Correct 141 ms 77944 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14584 KB Output is correct
2 Correct 447 ms 96784 KB Output is correct
3 Correct 508 ms 119652 KB Output is correct
4 Correct 439 ms 96888 KB Output is correct
5 Correct 423 ms 97040 KB Output is correct
6 Correct 467 ms 99960 KB Output is correct
7 Correct 392 ms 97288 KB Output is correct
8 Correct 521 ms 120312 KB Output is correct
9 Correct 337 ms 97600 KB Output is correct
10 Correct 15 ms 14456 KB Output is correct
11 Correct 460 ms 96968 KB Output is correct
12 Correct 536 ms 123516 KB Output is correct
13 Correct 446 ms 96888 KB Output is correct
14 Correct 408 ms 97012 KB Output is correct
15 Correct 472 ms 100600 KB Output is correct
16 Correct 361 ms 97648 KB Output is correct
17 Correct 508 ms 111096 KB Output is correct
18 Correct 338 ms 97512 KB Output is correct
19 Correct 15 ms 14456 KB Output is correct
20 Runtime error 522 ms 195704 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 15 ms 14456 KB Output is correct
2 Correct 15 ms 14968 KB Output is correct
3 Correct 16 ms 14968 KB Output is correct
4 Correct 16 ms 14968 KB Output is correct
5 Correct 18 ms 14968 KB Output is correct
6 Correct 19 ms 14968 KB Output is correct
7 Correct 16 ms 14968 KB Output is correct
8 Correct 16 ms 14968 KB Output is correct
9 Correct 16 ms 14992 KB Output is correct
10 Correct 16 ms 14968 KB Output is correct
11 Correct 16 ms 14968 KB Output is correct
12 Correct 15 ms 14584 KB Output is correct
13 Correct 447 ms 96784 KB Output is correct
14 Correct 508 ms 119652 KB Output is correct
15 Correct 439 ms 96888 KB Output is correct
16 Correct 423 ms 97040 KB Output is correct
17 Correct 467 ms 99960 KB Output is correct
18 Correct 392 ms 97288 KB Output is correct
19 Correct 521 ms 120312 KB Output is correct
20 Correct 337 ms 97600 KB Output is correct
21 Correct 15 ms 14456 KB Output is correct
22 Correct 460 ms 96968 KB Output is correct
23 Correct 536 ms 123516 KB Output is correct
24 Correct 446 ms 96888 KB Output is correct
25 Correct 408 ms 97012 KB Output is correct
26 Correct 472 ms 100600 KB Output is correct
27 Correct 361 ms 97648 KB Output is correct
28 Correct 508 ms 111096 KB Output is correct
29 Correct 338 ms 97512 KB Output is correct
30 Correct 15 ms 14584 KB Output is correct
31 Correct 124 ms 77944 KB Output is correct
32 Correct 136 ms 78044 KB Output is correct
33 Correct 128 ms 78092 KB Output is correct
34 Correct 126 ms 77944 KB Output is correct
35 Correct 126 ms 77944 KB Output is correct
36 Correct 144 ms 77948 KB Output is correct
37 Correct 137 ms 77972 KB Output is correct
38 Correct 143 ms 77900 KB Output is correct
39 Correct 145 ms 78000 KB Output is correct
40 Correct 130 ms 77992 KB Output is correct
41 Correct 133 ms 78012 KB Output is correct
42 Correct 139 ms 77944 KB Output is correct
43 Correct 141 ms 78172 KB Output is correct
44 Correct 141 ms 77944 KB Output is correct
45 Correct 15 ms 14456 KB Output is correct
46 Runtime error 522 ms 195704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Halted 0 ms 0 KB -