oj.uz

답안 #525373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525373 2022-02-11T13:41:32 Z Koosha_mv Designated Cities (JOI19_designated_cities) C++14
16 / 100
 363 ms 80228 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=1e6+99,inf=1e15;

int n,t,rt,X,Y,q,to[N],w[N],res[N],ans[N],pes[N];
pair<int,int> dp[N];
vector<int> g[N];

void dfs1(int u,int p){
	for(auto id : g[u]){
		int v=to[id];
		if(v==p) continue ;
		res[rt]+=w[id];
		dfs1(v,u);
	}
}
void dfs2(int u,int p){
	vector<pair<int,int> > vec(3);
	for(auto id : g[u]){
		int v=to[id];
		if(v==p) continue ;
		res[v]=res[u]-w[id]+w[id^1];
		dfs2(v,u);
		dp[v].F+=w[id];
		vec[0]=dp[v];
		sort(all(vec));
	}
	if(vec[2].S==0){
		dp[u]={0,u};
	}
	else{
		dp[u]=vec[2];
	}
	pes[u]=inf;
	if(vec[1].S!=0 && res[u]-vec[1].F-vec[2].F<ans[2]){
		ans[2]=res[u]-vec[1].F-vec[2].F;
		X=vec[1].S;
		Y=vec[2].S;
	}
	minm(ans[1],res[u]);
}
void find(){
	fill(ans,ans+N,inf);
	rt=1;
	while(g[rt].size()==1 && rt<n) rt++;
	dfs1(rt,0);
	dfs2(rt,0);
	if(n==2) ans[2]=0;
	//cout<<ans[1]<<" "<<ans[2]<<endl;
}

main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n;
	f(i,1,n){
		int u,v;
		cin>>u>>v>>w[2*i]>>w[2*i+1];
		to[2*i]=v;
		to[2*i+1]=u;
		g[u].pb(2*i);
		g[v].pb(2*i+1);
	}
	
	find();

	cin>>q;
	while(q--){
		int x;
		cin>>x;
		cout<<ans[x]<<'\n';
	}
}

Compilation message

designated_cities.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main(){
      | ^~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Incorrect 16 ms 31612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31624 KB Output is correct
2 Correct 299 ms 51420 KB Output is correct
3 Correct 337 ms 75868 KB Output is correct
4 Correct 241 ms 51476 KB Output is correct
5 Correct 235 ms 51388 KB Output is correct
6 Correct 281 ms 54972 KB Output is correct
7 Correct 214 ms 51508 KB Output is correct
8 Correct 315 ms 76636 KB Output is correct
9 Correct 157 ms 51892 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31540 KB Output is correct
2 Correct 245 ms 51528 KB Output is correct
3 Correct 363 ms 80228 KB Output is correct
4 Correct 242 ms 51628 KB Output is correct
5 Correct 259 ms 51700 KB Output is correct
6 Correct 272 ms 55872 KB Output is correct
7 Correct 162 ms 51964 KB Output is correct
8 Correct 321 ms 67256 KB Output is correct
9 Correct 154 ms 52056 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Incorrect 16 ms 31612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31624 KB Output is correct
2 Correct 299 ms 51420 KB Output is correct
3 Correct 337 ms 75868 KB Output is correct
4 Correct 241 ms 51476 KB Output is correct
5 Correct 235 ms 51388 KB Output is correct
6 Correct 281 ms 54972 KB Output is correct
7 Correct 214 ms 51508 KB Output is correct
8 Correct 315 ms 76636 KB Output is correct
9 Correct 157 ms 51892 KB Output is correct
10 Correct 17 ms 31540 KB Output is correct
11 Correct 245 ms 51528 KB Output is correct
12 Correct 363 ms 80228 KB Output is correct
13 Correct 242 ms 51628 KB Output is correct
14 Correct 259 ms 51700 KB Output is correct
15 Correct 272 ms 55872 KB Output is correct
16 Correct 162 ms 51964 KB Output is correct
17 Correct 321 ms 67256 KB Output is correct
18 Correct 154 ms 52056 KB Output is correct
19 Correct 18 ms 31608 KB Output is correct
20 Incorrect 271 ms 51608 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Incorrect 16 ms 31612 KB Output isn't correct
3 Halted 0 ms 0 KB -