oj.uz

답안 #261375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
261375 2020-08-11T16:51:41 Z dorijanlendvaj Designated Cities (JOI19_designated_cities) C++14
6 / 100
 2000 ms 119084 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]);
	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;
}

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];
                ~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 77816 KB Output is correct
2 Correct 97 ms 77912 KB Output is correct
3 Correct 87 ms 77816 KB Output is correct
4 Correct 93 ms 77816 KB Output is correct
5 Correct 81 ms 77816 KB Output is correct
6 Correct 96 ms 77900 KB Output is correct
7 Correct 92 ms 77816 KB Output is correct
8 Correct 91 ms 77816 KB Output is correct
9 Correct 106 ms 77816 KB Output is correct
10 Correct 101 ms 77820 KB Output is correct
11 Correct 88 ms 77816 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 77944 KB Output is correct
2 Execution timed out 2053 ms 119084 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 77816 KB Output is correct
2 Execution timed out 2094 ms 118016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 77816 KB Output is correct
2 Correct 97 ms 77912 KB Output is correct
3 Correct 87 ms 77816 KB Output is correct
4 Correct 93 ms 77816 KB Output is correct
5 Correct 81 ms 77816 KB Output is correct
6 Correct 96 ms 77900 KB Output is correct
7 Correct 92 ms 77816 KB Output is correct
8 Correct 91 ms 77816 KB Output is correct
9 Correct 106 ms 77816 KB Output is correct
10 Correct 101 ms 77820 KB Output is correct
11 Correct 88 ms 77816 KB Output is correct
12 Correct 96 ms 77904 KB Output is correct
13 Incorrect 101 ms 78840 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 77944 KB Output is correct
2 Execution timed out 2053 ms 119084 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 77816 KB Output is correct
2 Correct 97 ms 77912 KB Output is correct
3 Correct 87 ms 77816 KB Output is correct
4 Correct 93 ms 77816 KB Output is correct
5 Correct 81 ms 77816 KB Output is correct
6 Correct 96 ms 77900 KB Output is correct
7 Correct 92 ms 77816 KB Output is correct
8 Correct 91 ms 77816 KB Output is correct
9 Correct 106 ms 77816 KB Output is correct
10 Correct 101 ms 77820 KB Output is correct
11 Correct 88 ms 77816 KB Output is correct
12 Correct 95 ms 77944 KB Output is correct
13 Execution timed out 2053 ms 119084 KB Time limit exceeded
14 Halted 0 ms 0 KB -