oj.uz

Submission #261386

# Submission time Handle Problem Language Result Execution time Memory
261386 2020-08-11T16:57:08 Z dorijanlendvaj Designated Cities (JOI19_designated_cities) C++14
13 / 100
 965 ms 159312 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<=2000) 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:243:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (so.y.size()>k+1) so.y.pop_back();
          ~~~~~~~~~~~^~~~
designated_cities.cpp:244:21: 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 86 ms 77816 KB Output is correct
2 Correct 85 ms 77816 KB Output is correct
3 Correct 85 ms 77816 KB Output is correct
4 Correct 90 ms 77816 KB Output is correct
5 Correct 85 ms 77804 KB Output is correct
6 Correct 84 ms 77948 KB Output is correct
7 Correct 83 ms 77820 KB Output is correct
8 Correct 83 ms 77816 KB Output is correct
9 Correct 83 ms 77816 KB Output is correct
10 Correct 83 ms 77824 KB Output is correct
11 Correct 84 ms 77816 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 77816 KB Output is correct
2 Correct 940 ms 92664 KB Output is correct
3 Correct 965 ms 150392 KB Output is correct
4 Correct 860 ms 92792 KB Output is correct
5 Correct 819 ms 93864 KB Output is correct
6 Correct 877 ms 106480 KB Output is correct
7 Correct 825 ms 101792 KB Output is correct
8 Correct 933 ms 159312 KB Output is correct
9 Correct 725 ms 105496 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 77816 KB Output is correct
2 Incorrect 851 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 86 ms 77816 KB Output is correct
2 Correct 85 ms 77816 KB Output is correct
3 Correct 85 ms 77816 KB Output is correct
4 Correct 90 ms 77816 KB Output is correct
5 Correct 85 ms 77804 KB Output is correct
6 Correct 84 ms 77948 KB Output is correct
7 Correct 83 ms 77820 KB Output is correct
8 Correct 83 ms 77816 KB Output is correct
9 Correct 83 ms 77816 KB Output is correct
10 Correct 83 ms 77824 KB Output is correct
11 Correct 84 ms 77816 KB Output is correct
12 Correct 82 ms 77788 KB Output is correct
13 Incorrect 94 ms 78712 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 77816 KB Output is correct
2 Correct 940 ms 92664 KB Output is correct
3 Correct 965 ms 150392 KB Output is correct
4 Correct 860 ms 92792 KB Output is correct
5 Correct 819 ms 93864 KB Output is correct
6 Correct 877 ms 106480 KB Output is correct
7 Correct 825 ms 101792 KB Output is correct
8 Correct 933 ms 159312 KB Output is correct
9 Correct 725 ms 105496 KB Output is correct
10 Correct 83 ms 77816 KB Output is correct
11 Incorrect 851 ms 92792 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 77816 KB Output is correct
2 Correct 85 ms 77816 KB Output is correct
3 Correct 85 ms 77816 KB Output is correct
4 Correct 90 ms 77816 KB Output is correct
5 Correct 85 ms 77804 KB Output is correct
6 Correct 84 ms 77948 KB Output is correct
7 Correct 83 ms 77820 KB Output is correct
8 Correct 83 ms 77816 KB Output is correct
9 Correct 83 ms 77816 KB Output is correct
10 Correct 83 ms 77824 KB Output is correct
11 Correct 84 ms 77816 KB Output is correct
12 Correct 87 ms 77816 KB Output is correct
13 Correct 940 ms 92664 KB Output is correct
14 Correct 965 ms 150392 KB Output is correct
15 Correct 860 ms 92792 KB Output is correct
16 Correct 819 ms 93864 KB Output is correct
17 Correct 877 ms 106480 KB Output is correct
18 Correct 825 ms 101792 KB Output is correct
19 Correct 933 ms 159312 KB Output is correct
20 Correct 725 ms 105496 KB Output is correct
21 Correct 83 ms 77816 KB Output is correct
22 Incorrect 851 ms 92792 KB Output isn't correct
23 Halted 0 ms 0 KB -