oj.uz

답안 #261382

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

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 77944 KB Output is correct
2 Correct 86 ms 77816 KB Output is correct
3 Correct 83 ms 77816 KB Output is correct
4 Correct 101 ms 77820 KB Output is correct
5 Correct 85 ms 77816 KB Output is correct
6 Correct 82 ms 77816 KB Output is correct
7 Correct 84 ms 77816 KB Output is correct
8 Correct 86 ms 77868 KB Output is correct
9 Correct 85 ms 77816 KB Output is correct
10 Correct 85 ms 77828 KB Output is correct
11 Correct 82 ms 77816 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 77836 KB Output is correct
2 Execution timed out 2083 ms 117392 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 77944 KB Output is correct
2 Correct 86 ms 77816 KB Output is correct
3 Correct 83 ms 77816 KB Output is correct
4 Correct 101 ms 77820 KB Output is correct
5 Correct 85 ms 77816 KB Output is correct
6 Correct 82 ms 77816 KB Output is correct
7 Correct 84 ms 77816 KB Output is correct
8 Correct 86 ms 77868 KB Output is correct
9 Correct 85 ms 77816 KB Output is correct
10 Correct 85 ms 77828 KB Output is correct
11 Correct 82 ms 77816 KB Output is correct
12 Correct 87 ms 77816 KB Output is correct
13 Runtime error 193 ms 159352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 77944 KB Output is correct
2 Correct 86 ms 77816 KB Output is correct
3 Correct 83 ms 77816 KB Output is correct
4 Correct 101 ms 77820 KB Output is correct
5 Correct 85 ms 77816 KB Output is correct
6 Correct 82 ms 77816 KB Output is correct
7 Correct 84 ms 77816 KB Output is correct
8 Correct 86 ms 77868 KB Output is correct
9 Correct 85 ms 77816 KB Output is correct
10 Correct 85 ms 77828 KB Output is correct
11 Correct 82 ms 77816 KB Output is correct
12 Correct 82 ms 77816 KB Output is correct
13 Execution timed out 2074 ms 117940 KB Time limit exceeded
14 Halted 0 ms 0 KB -