Submission #450873

#	Time	Username	Problem	Language	Result	Execution time	Memory
450873		joshjms	Traffic (IOI10_traffic)	C++14	50 / 100	173 ms	45008 KiB

traffic

#include "traffic.h"

#include <bits/stdc++.h>
 
#define KON using
#define AQUA namespace std;
 
KON AQUA
 
#define ll long long
#define pb push_back
#define fi first
#define se second
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define debug(x) cout << #x << " => " << x << "\n";
#define sp " "
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
const int inf = 0x3f3f3f3f;
//const int INFF = 1e18 + 5;
const int INF = 2e9 + 5;
const int MX = 3e5 + 5;
const int MXL = 105;
const int mod = 1e9 + 7;
const double ERROR = 1e-5;

int arr[MX], max_cong[MX], total;
pair <int,int> ans = {INF, INF};
vector <int> E[MX];
bool vis[MX];

int dfs(int pos){
    int sum = arr[pos], res = 0;

    for(auto i:E[pos]){
        if(vis[i]) continue;

        vis[i] = 1;

        int ret = dfs(i);
        res = max(res, ret);
        sum += ret;
    }

    res = max(res, total - sum);

    max_cong[pos] = res;
    return sum;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    for(int i = 0; i < N; i++){
        arr[i] = pp[i];
        total += arr[i];
    }
    for(int i = 0; i < N - 1; i++){
        E[S[i]].pb(D[i]);
        E[D[i]].pb(S[i]);
    }
    vis[0] = 1;
    dfs(0);
    for(int i = 0; i < N; i++)
        ans = min(ans, {max_cong[i], i});
    return ans.se;
}

/*

static int N,P[1000000],S[1000000],D[1000000];

int32_t main(){
    int i;
    scanf("%d",&N);
    for (i=0;i<N;i++) scanf("%d",&P[i]);
    for (i=0;i<N-1;i++) scanf("%d%d",&S[i],&D[i]);
    int r = LocateCentre(N,P,S,D);
    printf("%d\n",r);
    return 0;
}

*/

• Subtask 1: 25 / 25
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 25