Submission #1174322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174322		3lektra	Traffic (IOI10_traffic)	C++20	100 / 100	537 ms	157032 KiB

traffic

#include<bits/stdc++.h>
#include "traffic.h"
using namespace std;

const int maxN = 1e6+1;

int n;
int fans[maxN];
int t_fans = 0;
vector<int> paths[maxN];
//bool vis[maxN];
int dp[maxN][2]; // 0 = Total number of fans in the subtree // 1 = best option

void dfs(int node, int par){
    dp[node][0] = fans[node];
    int mx_fans = 0;

    for(int i : paths[node]){
        if(i != par){
            dfs(i, node);
            dp[node][0] += dp[i][0]; 
            mx_fans = max(mx_fans, dp[i][0]);
        }
    }
    //cout << node << ' ' << mx_fans << '\n';
    dp[node][1] = max(mx_fans, t_fans - dp[node][0]);
}


int LocateCentre(int N, int pp[], int S[], int D[]) {
    n = N;
    memset(fans, 0, sizeof(fans));
    //memset(vis, false, sizeof(fans));
    for(int i = 0; i < n; ++i){
        fans[i] = pp[i];
        t_fans += pp[i];
        if(i != n-1){
            paths[S[i]].push_back(D[i]);
            paths[D[i]].push_back(S[i]);
        }
    }
    dfs(0,0);
    //for(int i = 0; i < n; ++i) cout << dp[i][0] << ' ' << dp[i][1] << '\n';
    int ans = 0;
    for(int i = 0; i < n; ++i){
        if(dp[i][1] < dp[ans][1]) ans = i;
    }
    //cout << dp[ans][1] << '\n';
    return ans;
}

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