oj.uz

Submission #261383

# Submission time Handle Problem Language Result Execution time Memory
261383 2020-08-11T16:55:43 Z dorijanlendvaj Designated Cities (JOI19_designated_cities) C++14
6 / 100
 2000 ms 157816 KB 
//DUEL
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define all(a) begin(a),end(a)

using namespace std;
using namespace __gnu_pbds;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w,bool fl=false)
{
	cout<<w.size()<<en;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<en;
	if (fl) cout<<flush;
}

void M998()
{
	swap(MOD,MOD2);
}

ll raand()
{
	ll a=rund();
	a*=RAND_MAX;
	a+=rund();
    return a;
}

#define rand raand

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

void compress(vi&v)
{
	set<int> s;
	for (auto a: v) s.insert(a);
	vi o(all(s));
	for (auto&a: v) a=lower_bound(all(o),a)-o.begin();
}

void compress(vl&v)
{
	set<ll> s;
	for (auto a: v) s.insert(a);
	vl o(all(s));
	for (auto&a: v) a=lower_bound(all(o),a)-o.begin();
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a,int base=10)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=base;
		k+=a[i]-'0';
	}
	return k;
}

template<class T>
void eras(vector<T>& a,T b)
{
	a.erase(find(a.begin(),a.end(),b));
}

string its(ll k,int base=10)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%base)+'0');
		k/=base;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

ll gcd(ll a,ll b)
{
	if (b==0) return a;
	return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

inline int sub(int a,int b)
{
	if (a-b>=0) return a-b;
	return a-b+MOD;
}

inline int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

const int N=300010;
int t,n,k;
ll an[N],s;
gp_hash_table<int,int> c[N];
vi ch[N];
vl dp[N];

pair<vl,vl> mer(pair<vl,vl> a,vl b)
{
	vl x=a.x,y=a.y;
	vl u(x.size()+b.size()-1),v(x.size()+b.size()-1),w(y.size()+b.size()-1);
	for (int i=0;i<x.size();++i) for (int j=0;j<b.size();++j) u[i+j]=max(u[i+j],x[i]+b[j]);
	for (int i=1;i<x.size();++i) for (int j=1;j<b.size();++j) v[i+j]=max(v[i+j],x[i]+b[j]);
	for (int i=2;i<y.size();++i) for (int j=0;j<b.size();++j) w[i+j]=max(w[i+j],y[i]+b[j]);
	vl no;
	for (int i=0;i<max(v.size(),w.size());++i)
	{
		ll z=0;
		if (i<v.size()) z=max(z,v[i]);
		if (i<w.size()) z=max(z,w[i]);
		no.pb(z);
	}
	return {u,no};
}

void dfs(int i,int p=-1,ll co=0)
{
	pair<vl,vl> so=mp(vl(2,0),vl(2,0));
	vector<pii> vv;
	for (auto a: ch[i]) if (a!=p)
	{
		dfs(a,i,co+c[i][a]-c[a][i]);
		s-=c[a][i];
		for (int j=1;j<dp[a].size();++j) dp[a][j]+=c[i][a];
		//so=mer(so,dp[a]);
		vv.eb(dp[a].size(),a);
	}
	sort(all(vv));
	for (auto a: vv) so=mer(so,dp[a.y]);
	while (so.y.size()>k+1) so.y.pop_back();
	while (so.x.size()>k+1) so.x.pop_back();
	for (int i=1;i<=min(k,(int)so.y.size());++i) an[i]=max(an[i],so.y[i]+co);
	/*cout<<i<<endl;
	prVec(so.x);
	prVec(so.y);
	cout<<endl;*/
	dp[i]=so.x;
	//cout<<i<<' '<<dp[i].size()<<en;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)+13893829);
	cin>>n;
	if (n<=18) k=2000;
	else k=2;
	//k=min(n,4000000/n);
	for (int i=1;i<n;++i)
	{
		int a,b,x,y;
		cin>>a>>b>>x>>y;
		ch[a].pb(b);
		ch[b].pb(a);
		c[a].insert({b,x});
		c[b].insert({a,y});
		s+=x;
		s+=y;
	}
	dfs(1);
	int q;
	cin>>q;
	while (q--)
	{
		int u;
		cin>>u;
		assert(u<=k);
		cout<<s-an[u]<<en;
	}
}

Compilation message

designated_cities.cpp: In function 'std::pair<std::vector<long long int>, std::vector<long long int> > mer(std::pair<std::vector<long long int>, std::vector<long long int> >, std::vector<long long int>)':
designated_cities.cpp:213:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<x.size();++i) for (int j=0;j<b.size();++j) u[i+j]=max(u[i+j],x[i]+b[j]);
               ~^~~~~~~~~
designated_cities.cpp:213:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<x.size();++i) for (int j=0;j<b.size();++j) u[i+j]=max(u[i+j],x[i]+b[j]);
                                            ~^~~~~~~~~
designated_cities.cpp:214:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1;i<x.size();++i) for (int j=1;j<b.size();++j) v[i+j]=max(v[i+j],x[i]+b[j]);
               ~^~~~~~~~~
designated_cities.cpp:214:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1;i<x.size();++i) for (int j=1;j<b.size();++j) v[i+j]=max(v[i+j],x[i]+b[j]);
                                            ~^~~~~~~~~
designated_cities.cpp:215:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=2;i<y.size();++i) for (int j=0;j<b.size();++j) w[i+j]=max(w[i+j],y[i]+b[j]);
               ~^~~~~~~~~
designated_cities.cpp:215:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=2;i<y.size();++i) for (int j=0;j<b.size();++j) w[i+j]=max(w[i+j],y[i]+b[j]);
                                            ~^~~~~~~~~
designated_cities.cpp:217:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<max(v.size(),w.size());++i)
               ~^~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:220:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i<v.size()) z=max(z,v[i]);
       ~^~~~~~~~~
designated_cities.cpp:221:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i<w.size()) z=max(z,w[i]);
       ~^~~~~~~~~
designated_cities.cpp: In function 'void dfs(int, int, ll)':
designated_cities.cpp:235:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1;j<dp[a].size();++j) dp[a][j]+=c[i][a];
                ~^~~~~~~~~~~~~
designated_cities.cpp:241:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (so.y.size()>k+1) so.y.pop_back();
         ~~~~~~~~~~~^~~~
designated_cities.cpp:242:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (so.x.size()>k+1) so.x.pop_back();
         ~~~~~~~~~~~^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 77816 KB Output is correct
2 Correct 104 ms 77948 KB Output is correct
3 Correct 97 ms 77816 KB Output is correct
4 Correct 88 ms 77816 KB Output is correct
5 Correct 83 ms 77816 KB Output is correct
6 Correct 91 ms 77816 KB Output is correct
7 Correct 99 ms 77816 KB Output is correct
8 Correct 95 ms 77852 KB Output is correct
9 Correct 94 ms 77816 KB Output is correct
10 Correct 94 ms 77848 KB Output is correct
11 Correct 87 ms 77816 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 77816 KB Output is correct
2 Correct 881 ms 92844 KB Output is correct
3 Correct 949 ms 156860 KB Output is correct
4 Correct 884 ms 97880 KB Output is correct
5 Execution timed out 2105 ms 101544 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 77816 KB Output is correct
2 Incorrect 869 ms 92792 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 77816 KB Output is correct
2 Correct 104 ms 77948 KB Output is correct
3 Correct 97 ms 77816 KB Output is correct
4 Correct 88 ms 77816 KB Output is correct
5 Correct 83 ms 77816 KB Output is correct
6 Correct 91 ms 77816 KB Output is correct
7 Correct 99 ms 77816 KB Output is correct
8 Correct 95 ms 77852 KB Output is correct
9 Correct 94 ms 77816 KB Output is correct
10 Correct 94 ms 77848 KB Output is correct
11 Correct 87 ms 77816 KB Output is correct
12 Correct 82 ms 77816 KB Output is correct
13 Runtime error 180 ms 157816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 77816 KB Output is correct
2 Correct 881 ms 92844 KB Output is correct
3 Correct 949 ms 156860 KB Output is correct
4 Correct 884 ms 97880 KB Output is correct
5 Execution timed out 2105 ms 101544 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 77816 KB Output is correct
2 Correct 104 ms 77948 KB Output is correct
3 Correct 97 ms 77816 KB Output is correct
4 Correct 88 ms 77816 KB Output is correct
5 Correct 83 ms 77816 KB Output is correct
6 Correct 91 ms 77816 KB Output is correct
7 Correct 99 ms 77816 KB Output is correct
8 Correct 95 ms 77852 KB Output is correct
9 Correct 94 ms 77816 KB Output is correct
10 Correct 94 ms 77848 KB Output is correct
11 Correct 87 ms 77816 KB Output is correct
12 Correct 97 ms 77816 KB Output is correct
13 Correct 881 ms 92844 KB Output is correct
14 Correct 949 ms 156860 KB Output is correct
15 Correct 884 ms 97880 KB Output is correct
16 Execution timed out 2105 ms 101544 KB Time limit exceeded
17 Halted 0 ms 0 KB -