oj.uz

Submission #1088391

# Submission time Handle Problem Language Result Execution time Memory
1088391 2024-09-14T10:18:44 Z tht2005 Designated Cities (JOI19_designated_cities) C++17
33 / 100
 579 ms 79184 KB 
#include <bits/stdc++.h>
#include <type_traits>
using namespace std;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(),x.end()
auto& errStream=cerr;
#ifdef LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"(";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<")";
}

ll read(){
	ll i;
	scanf("%"  SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

template<class T>
void print(const vector<T>&v){
	REP(i,v.size())
		print(v[i],i==int(v.size())-1?1:2);
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

constexpr ll TEN(int n){
	return n==0?1:TEN(n-1)*10;
}

template<class T>
vector<T> Uniqued(const vector<T>&vv){
	auto v(vv);
	sort(ALL(v));
	v.erase(unique(ALL(v)),v.end());
	return v;
}
template<class T>
void MakeUniqued(vector<T>&v){
	sort(ALL(v));
	v.erase(unique(ALL(v)),v.end());
}

const int Nmax=200010;
int cost[Nmax*2];
vector<pi> tr[Nmax];
int n,ans[Nmax],inCost[Nmax];

int dfs1(int v,int p){
	int res=0;
	for(auto e:tr[v])if(e.first!=p){
		res+=cost[e.second^1];
		res+=dfs1(e.first,v);
	}
	return res;
}

void dfs2(int v,int p,int cur){
	inCost[v]=cur;
	for(auto e:tr[v])if(e.first!=p){
		dfs2(e.first,v,cur+cost[e.second]-cost[e.second^1]);
	}
}

void Solve1(){
	inCost[0]=dfs1(0,-1);
	dfs2(0,-1,inCost[0]);
	ans[1]=*max_element(inCost,inCost+n);
}

pi dfs3(int v,int p,tuple<int,int,int>&dst){
	pi res(inCost[v],v);
	for(auto e:tr[v])if(e.first!=p){
		pi w=dfs3(e.first,v,dst);
		w.first+=cost[e.second]+cost[e.second^1];
		chmax(dst,make_tuple(res.first+w.first,res.second,w.second));
		chmax(res,w);
	}
	return res;
}

pi Solve2(){
	tuple<int,int,int> res(-1,-1,-1);
	dfs3(0,-1,res);
	ans[2]=get<0>(res)/2;
	return pi(get<1>(res),get<2>(res));
}

struct TopK{
	int k,sum;
	multiset<int> lw,up;
	TopK(int kk){
		k=kk;
		sum=0;
	}
	void Add(int v){
		sum+=v;
		up.insert(v);
		if(int(up.size())>k){
			auto itr=up.begin();
			lw.insert(*itr);
			sum-=*itr;
			up.erase(itr);
		}
	}
	void Del(int v){
		auto itr=lw.find(v);
		if(itr!=lw.end()){
			lw.erase(itr);
			return;
		}
		itr=up.find(v);
		sum-=v;
		up.erase(itr);
		if(!lw.empty()){
			itr=prev(lw.end());
			sum+=*itr;
			up.insert(*itr);
			lw.erase(itr);
		}
	}
	int GetSum(){
		return sum;
	}
};

int maxDep[Nmax];
int dfs4(int v,int p,int pCost,TopK& tk){
	int res=0;
	for(auto e:tr[v])if(e.first!=p){
		int w=dfs4(e.first,v,cost[e.second],tk);
		tk.Add(min(res,w));
		chmax(res,w);
	}
	return maxDep[v]=res+pCost;
}

int dfs5(int v,int p,int pPath,TopK&tk){
	int res=inCost[v]+tk.GetSum();
	vector<pi> ch;
	vi mx1,mx2;
	for(auto e:tr[v])if(e.first!=p){
		ch.PB(e);
		mx1.PB(maxDep[e.first]);
		mx2.PB(maxDep[e.first]);
	}
	int s=ch.size();
	REP(i,s-1)
		chmax(mx1[i+1],mx1[i]);
	for(int i=s-1;i>=1;i--)
		chmax(mx2[i-1],mx2[i]);
	REP(i,s){
		int to=ch[i].first,idx=ch[i].second;
		int m=pPath;
		if(i>0)chmax(m,mx1[i-1]);
		if(i+1<s)chmax(m,mx2[i+1]);
		tk.Del(maxDep[to]);
		tk.Add(maxDep[to]-cost[idx]);
		tk.Del(m);
		tk.Add(m+cost[idx^1]);
		chmax(res,dfs5(to,v,m+cost[idx^1],tk));
		tk.Add(maxDep[to]);
		tk.Del(maxDep[to]-cost[idx]);
		tk.Add(m);
		tk.Del(m+cost[idx^1]);
	}
	return res;
}

int Solve3(int k){
	TopK tk(k-1);
	dfs4(0,-1,0,tk);
	tk.Add(maxDep[0]);
	return dfs5(0,-1,0,tk);
}

signed main(){
	n=read();
	assert(n<=Nmax);
	int sum=0;
	REP(i,n-1){
		int a=read()-1,b=read()-1,c=read(),d=read();
		tr[a].EB(b,i*2);
		cost[i*2]=c;
		tr[b].EB(a,i*2+1);
		cost[i*2+1]=d;
		sum+=c+d;
	}
	Solve1();
	Solve2();
	int q=read();
	assert(q==1);
	int e=read();
	if(e<=2){
		print(sum-ans[e]);
		return 0;
	}
	int a=Solve3(e);
	print(sum-a);
}

Compilation message

designated_cities.cpp: In function 'll read()':
designated_cities.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%"  SCNd64,&i);
      |  ~~~~~^~~~~~~~~~~~~~~~
designated_cities.cpp: In function 'std::string readString()':
designated_cities.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  scanf("%s",buf);
      |  ~~~~~^~~~~~~~~~
designated_cities.cpp: In function 'char* readCharArray()':
designated_cities.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |  scanf("%s",ret);
      |  ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 10076 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 124 ms 19804 KB Output is correct
3 Correct 172 ms 33128 KB Output is correct
4 Correct 121 ms 19792 KB Output is correct
5 Correct 111 ms 19968 KB Output is correct
6 Correct 126 ms 21836 KB Output is correct
7 Correct 107 ms 19392 KB Output is correct
8 Correct 164 ms 33360 KB Output is correct
9 Correct 82 ms 19128 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 132 ms 19988 KB Output is correct
3 Correct 187 ms 34896 KB Output is correct
4 Correct 121 ms 19796 KB Output is correct
5 Correct 119 ms 19908 KB Output is correct
6 Correct 129 ms 22096 KB Output is correct
7 Correct 88 ms 19132 KB Output is correct
8 Correct 135 ms 28340 KB Output is correct
9 Correct 90 ms 19084 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 10076 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 124 ms 19804 KB Output is correct
3 Correct 172 ms 33128 KB Output is correct
4 Correct 121 ms 19792 KB Output is correct
5 Correct 111 ms 19968 KB Output is correct
6 Correct 126 ms 21836 KB Output is correct
7 Correct 107 ms 19392 KB Output is correct
8 Correct 164 ms 33360 KB Output is correct
9 Correct 82 ms 19128 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 132 ms 19988 KB Output is correct
12 Correct 187 ms 34896 KB Output is correct
13 Correct 121 ms 19796 KB Output is correct
14 Correct 119 ms 19908 KB Output is correct
15 Correct 129 ms 22096 KB Output is correct
16 Correct 88 ms 19132 KB Output is correct
17 Correct 135 ms 28340 KB Output is correct
18 Correct 90 ms 19084 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 545 ms 31076 KB Output is correct
21 Correct 168 ms 41528 KB Output is correct
22 Correct 554 ms 35972 KB Output is correct
23 Correct 499 ms 37836 KB Output is correct
24 Correct 483 ms 36436 KB Output is correct
25 Correct 560 ms 37604 KB Output is correct
26 Correct 520 ms 36896 KB Output is correct
27 Correct 540 ms 38928 KB Output is correct
28 Correct 554 ms 45876 KB Output is correct
29 Correct 523 ms 38224 KB Output is correct
30 Correct 510 ms 38584 KB Output is correct
31 Correct 526 ms 42780 KB Output is correct
32 Correct 579 ms 79184 KB Output is correct
33 Correct 414 ms 47284 KB Output is correct

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 10076 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -