Submission #309601

#	Time	Username	Problem	Language	Result	Execution time	Memory
309601		ShiftyBlock	Traffic (IOI10_traffic)	C++11	100 / 100	1435 ms	156408 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pb push_back
#define ll long long
void setIO(string name, int submit) {
    if (submit) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
const int MAXN=1e6;
vector<int> adj[MAXN];
int dp[MAXN];
void dfs(int cur, int par, int P[]){
    dp[cur]= P[cur];
    for (int next: adj[cur]) {
        if(next==par) continue;
        dfs(next, cur, P);
        dp[cur]+=dp[next];
    }
}
int LocateCentre(int N, int P[], int s[], int d[]){
    for (int i = 0; i < N-1; ++i) {
        adj[s[i]].pb(d[i]);
        adj[d[i]].pb(s[i]);
    }
    dfs(0, -1, P);
    deque<int> dq;
    dq.pb(0);
    bool visited[MAXN];
    for (int i = 0; i < N; ++i) {
        visited[i]=false;
    }
    visited[0]=true;
    int min[MAXN]={};
    for (int i = 0; i < N; ++i) {
        min[i]=1<<30;
    }


    while(dq.size()>0){
       int node= dq.front(); dq.pop_front();
       int best=0;
       for(int next: adj[node]){
           if(visited[next]){
               best=max(best,dp[0]-dp[node]); continue;
           }
           best= max(best, dp[next]);
           dq.pb(next);
           visited[next]=true;
       }
       min[node]= best;
    }
    int val=1<<30;
    int idx=-1;
    for (int i = 0; i < N; ++i) {
        if(min[i]<val){
            idx=i; val=min[i];
        }
    }
    return idx;

}
/*int main() {
    setIO("traffic", 0);
    int N=5;
    int arr[]{10,10,10,20,20};
    int left[]{0, 1, 2, 3};
    int right[]{2, 2, 3, 4};
    cout << LocateCentre(N, arr, left, right);
    return 0;
}
*/

Compilation message (stderr)

traffic.cpp: In function 'void setIO(std::string, int)':
traffic.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   10 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffic.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   11 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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