Submission #153293

#	Time	Username	Problem	Language	Result	Execution time	Memory
153293		username	Designated Cities (JOI19_designated_cities)	C++14	16 / 100	502 ms	44924 KiB

designated_cities

#include<bits/stdc++.h>
#define int int64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define MAX(x,y) (x=max(x,(y)))
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)

struct tup{int f,s,t;};
const int maxn=2e5+9;
int n,q,s=0,k=0,x=0,res[maxn];
vector<tup>g[maxn];
vector<int>ch;

pii far(int u,int f){
	pii ret={0,u};
	REP(i,0,g[u].size()){
		tup&e=g[u][i];
		if(e.f==f)continue;
		pii tt=far(e.f,u);
		MAX(ret,pii(tt.f+e.s,tt.s));
	}
	return ret;
}

int tdc(int u,int f){
	int mx=0;
	REP(i,0,g[u].size()){
		tup&e=g[u][i];
		if(e.f==f){
			k+=e.s;
			continue;
		}
		int t=tdc(e.f,u)+e.s;
		if(t>mx){
			if(mx>0)ch.pb(mx);
			mx=t;
		}
	}
	return mx;
}

void dfs(int u,int f){
	REP(i,0,g[u].size()){
		tup&e=g[u][i];
		if(e.f==f){
			x+=e.s;
			continue;
		}
		dfs(e.f,u);
	}
}

void calc(int u,int f){
	MAX(res[1],x);
	REP(i,0,g[u].size()){
		tup&e=g[u][i];
		if(e.f==f)continue;
		x+=e.s-e.t;
		calc(e.f,u);
		x-=e.s-e.t;
	}
}

main(){
	IOS;
	cin>>n;
	REP(i,1,n){
		int a,b,c,d;cin>>a>>b>>c>>d,--a,--b;
		g[a].pb(tup{b,c,d});
		g[b].pb(tup{a,d,c});
		s+=c+d;
	}
	ch.pb(tdc(far(far(0,-1).s,-1).s,-1));
	sort(ch.begin(),ch.end(),[](int a,int b){return a>b;});
	res[1]=k;
	REP(i,2,n+1)res[i]=res[i-1]+(i-2<ch.size()?ch[i-2]:0);
	dfs(0,-1);
	calc(0,-1);
	cin>>q;
	REP(i,0,q){
		int e;cin>>e;
		cout<<s-res[e]<<endl;
	}
}

Compilation message (stderr)

designated_cities.cpp: In function 'pii far(int64_t, int64_t)':
designated_cities.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
designated_cities.cpp:21:2: note: in expansion of macro 'REP'
  REP(i,0,g[u].size()){
  ^~~
designated_cities.cpp: In function 'int64_t tdc(int64_t, int64_t)':
designated_cities.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
designated_cities.cpp:32:2: note: in expansion of macro 'REP'
  REP(i,0,g[u].size()){
  ^~~
designated_cities.cpp: In function 'void dfs(int64_t, int64_t)':
designated_cities.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
designated_cities.cpp:48:2: note: in expansion of macro 'REP'
  REP(i,0,g[u].size()){
  ^~~
designated_cities.cpp: In function 'void calc(int64_t, int64_t)':
designated_cities.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
designated_cities.cpp:60:2: note: in expansion of macro 'REP'
  REP(i,0,g[u].size()){
  ^~~
designated_cities.cpp: At global scope:
designated_cities.cpp:69:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:81:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  REP(i,2,n+1)res[i]=res[i-1]+(i-2<ch.size()?ch[i-2]:0);
                               ~~~^~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44