Submission #1109078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109078		aguss	Traffic (IOI10_traffic)	C++14	0 / 100	2 ms	4432 KiB

traffic

#include <bits/stdc++.h>

#define _USE_MATH_DEFINES
#define INF LLONG_MAX
#define MOD 1000000007

#define endl "\n"
#define sp " "

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define f1(i, x) for(auto &i : x)
#define f2(i, x, j) for(ll i = j; i < x; i++)

#define raya() cout << endl << "====================================" << endl
#define dbg(x) cerr << #x << ": " << x << endl;

using namespace std;
using ll = long long;
int sum = 0;
vector<vector<int>> sum1, sum2, arr;
vector<int> P;
vector<bool> vis;
ll dfs(int n){
    if(vis[n]) return 0;
    vis[n] = 1; 
    if(arr[n].size() == 1){
        sum1[n].push_back(0);
        return P[n];
    } else {
        f1(i, arr[n]){
            int aux;
            aux = dfs(i);
            if(aux){
                sum1[n].push_back(aux);
            }
        }
    }
    int ans = 0;
    f1(i, sum1[n]){
        ans += i;
    }
    sum1[n].push_back(sum - ans - P[n]);
    return ans + P[n];
}
int LocateCentre(int n, int p[], int s[], int d[]){
    arr.assign(n, vector<int>(0));
    sum1.assign(n, vector<int>(0));
    sum2.assign(n, vector<int>(0));
    f2(i, n, 0){
        P.push_back(p[i]);
        sum += P[i];
    }
    vis.assign(n, 0);
    int r;
    f2(i, n - 1, 0){
        arr[s[i]].push_back(d[i]);
        arr[d[i]].push_back(s[i]);
    }
    r = 0;
    dfs(r);
    int ans = -1;
    f1(i, sum1){
        int aux = 0;
        f1(j, i){
            aux = max(j, aux);
        }
        if(ans == -1){
            ans = aux;
        }
        ans = max(ans, aux);
    }
    return ans;
}

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