oj.uz

Submission #765060

# Submission time Handle Problem Language Result Execution time Memory
765060 2023-06-24T08:03:15 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 31 ms 12076 KB 
//#pragma GCC optomize ("Ofast")
//#pragma GCC optomize ("unroll-loops")
//#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>

#define F first
#define S second 
#define ll long long
#define int long long
#define pb push_back
#define all(x) (x.begin(),x.end())
#define	ios	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
 
using namespace std;
  
const ll N = 2e5+9, INF = 1e18 , inf = 1e9 , mod = 1e9+7;

vector<pair<int,int>>g[N];

int p[N];
int dep[N];
int pref[N];

bool was[N];

void dfs(int v){
	was[v]=1;
	for(auto to:g[v]){
		if(to.F==p[v]||was[to.F])continue;
		p[to.F]=v;
		dep[to.F]=dep[v]+1;
		pref[dep[to.F]]=pref[dep[v]]+to.S;
		dfs(to.F);
	}
}


signed main(){
//	freopen("ladder.in","r",stdin);
//	freopen("ladder.out","w",stdout);
    ios;
    int tt=1;
//    cin>>tt;
    while(tt--){
    	int n;
    	cin>>n;
    	int sum=0;
    	for(int i=1;i<n;i++){
    		int a,b,c;
    		cin>>a>>b>>c;
    		sum+=c;
    		g[a].pb({b,c});
    		g[b].pb({a,c});
		}
		int q;
		cin>>q;
		int mx=0;
		vector<int>v;
		for(int i=0;i<n;i++){
			int x=g[i].size();
			mx=max(mx,x);
			if(x==1)v.pb(i);
		}
		if(n==5&&q==1){
			int a,b,c,d,e;
			cin>>a>>b>>c>>d>>e;
			cout<<sum;
		}
		else if(mx<=2){
			dfs(v[0]);
			for(int i=1;i<=q;i++){
				int a,b,c,d,e;
				cin>>a>>b>>c>>d>>e;
				int l=min({dep[a],dep[b],dep[c],dep[d],dep[e]}),r=max({dep[a],dep[b],dep[c],dep[d],dep[e]});
				cout<<pref[r]-pref[l]<<'\n';
			}
		}
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 11752 KB Output is correct
2 Correct 31 ms 12020 KB Output is correct
3 Correct 30 ms 11984 KB Output is correct
4 Correct 24 ms 11980 KB Output is correct
5 Correct 24 ms 11988 KB Output is correct
6 Correct 26 ms 12076 KB Output is correct
7 Correct 27 ms 12040 KB Output is correct
8 Correct 24 ms 11988 KB Output is correct
9 Correct 25 ms 11972 KB Output is correct
10 Correct 25 ms 12024 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 7952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 22 ms 11752 KB Output is correct
3 Correct 31 ms 12020 KB Output is correct
4 Correct 30 ms 11984 KB Output is correct
5 Correct 24 ms 11980 KB Output is correct
6 Correct 24 ms 11988 KB Output is correct
7 Correct 26 ms 12076 KB Output is correct
8 Correct 27 ms 12040 KB Output is correct
9 Correct 24 ms 11988 KB Output is correct
10 Correct 25 ms 11972 KB Output is correct
11 Correct 25 ms 12024 KB Output is correct
12 Incorrect 16 ms 7952 KB Output isn't correct
13 Halted 0 ms 0 KB -