Submission #1219105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219105		Theo830	Traffic (IOI10_traffic)	C++20	0 / 100	0 ms	320 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define id pair<ll,vector<ll> >
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "traffic.h"
vector<vector<ll> > adj;
ll sum = 0;
ll ex[1000005];
ll sumi[100005] = {0};
int ans = 0;
ll res = 2e9+5;
void build(ll idx,ll p){
    sumi[idx] += ex[idx];
    for(auto x:adj[idx]){
        if(x != p){
            build(x,idx);
            sumi[idx] += sumi[x];
        }
    }
}
void solve(ll idx,ll p){
    ll resi = 0;
    ll sumd = 0;
    for(auto x:adj[idx]){
        if(x != p){
            resi = max(resi,sumi[x]);
            sumd += sumi[x];
        }
    }
    resi = max(resi,sum - sumd);
    if(resi < res){
        res = resi;
        ans = idx;
    }
}
int LocateCentre(int n, int arr[], int a[], int b[]){
    adj.assign(n+5,vector<ll>());
    int ans = 0;
    int res = 2e9+5;
    f(i,0,n-1){
        adj[a[i]].pb(b[i]);
        adj[b[i]].pb(a[i]);
    }
    f(i,0,n){
        ex[i] = arr[i];
        sum += ex[i];
    }
    build(0,0);
    solve(0,0);
    return ans;
}

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