Submission #403163

#	Time	Username	Problem	Language	Result	Execution time	Memory
403163		fidgetspinnerkid	Traffic (IOI10_traffic)	C++11	100 / 100	1334 ms	156816 KiB

traffic

#include <bits/stdc++.h> // see /general/running-code-locally
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
	if (sz(name)) {
		freopen((name+".in").c_str(), "r", stdin); // see /general/io
		freopen((name+".out").c_str(), "w", stdout);
	}
}

const int SZ = 1000000;

int n, p[SZ];

vector<int> adjlist[SZ];

int pref[SZ+1];
int ans[SZ];

void dfs(int node, int prev) {
    ans[node] = 0;
    for(int v: adjlist[node]) {
        if(v==prev) {
            ans[node] = max(ans[node], pref[0] - pref[node]);
            continue;
        } 
        ans[node] = max(ans[node], pref[v]);
        dfs(v, node);
    }
}

int fill_pre(int node, int prev) {
    pref[node] = p[node];
    
    for(int v: adjlist[node]) {
        if(v==prev) {
            continue;
        }
        fill_pre(v, node);
        pref[node] += pref[v];
    }
    return pref[node];
}

int LocateCentre(int nc, int pc[], int sc[], int dc[] ) {

    n = nc;
    for(int i=0; i<n; i++) {
        p[i] = pc[i];
    }
    for(int i=0; i<n-1; i++) {
        adjlist[sc[i]].push_back(dc[i]);
        adjlist[dc[i]].push_back(sc[i]);
    }

    fill_pre(0, -1);
    dfs(0, -1);

    int sol;
    int min_cong = 2000000001;
    for(int i=0; i<n; i++) {
        if(min_cong>ans[i]) {
            min_cong = ans[i];
            sol = i;
        }
    }

    return sol;

}

Compilation message (stderr)

traffic.cpp: In function 'void setIO(std::string)':
traffic.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen((name+".in").c_str(), "r", stdin); // see /general/io
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffic.cpp:20:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   freopen((name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:81:12: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     return sol;
      |            ^~~

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