oj.uz

Submission #278793

# Submission time Handle Problem Language Result Execution time Memory
278793 2020-08-21T22:16:02 Z ec1117 Traffic (IOI10_traffic) C++17
0 / 100
 16 ms 23808 KB 
#include "bits/stdc++.h"
#include "traffic.h"
using namespace std;

#define pb push_back
#define mp make_pair

typedef vector<int> vi;

vi adj[1000001];
long long w[1000001];
long long sum[1000001];
int pars[1000001];

void dfs(int n, int par){
    pars[n]=par;
    sum[n]+=w[n];
    for(int x:adj[n]){
        if(x!=par){
            dfs(x,n);
        }
        sum[n]+=sum[x];
    }
}

int LocateCentre(int n, int p[], int s[], int d[]){//int[] s?
    long long tsum=0;
    for(int i=0;i<n;i++){
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
    }
    for(int i=0;i<n;i++){
        w[i]=p[i];
        tsum+=p[i];
    }
    dfs(0,-1);
    int ret=0;
    long long mins=LLONG_MAX;
    pars[0]=0;
    for(int i=0;i<n;i++){
        long long tmp=0;
        for(int j:adj[i]){
            if(j!=pars[i]) {
                tmp = max(tmp, sum[j]);
            }
        }
        tmp=max(tmp,tsum-sum[pars[i]]);
        if(tmp<mins){
            mins=tmp;
            ret=i;
        }
    }
    return ret;
}

//int main(){
//    int n;
//    cin >> n;
//    int p[n],s[n],d[n];
//    for(int i=0;i<n;i++)cin >>p[i];
//    for(int i=0;i<n;i++)cin >>s[i];
//    for(int i=0;i<n;i++)cin >>d[i];
//    cout << LocateCentre(n,p,s,d);
//    return 0;
//}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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