Submission #474477

#	Time	Username	Problem	Language	Result	Execution time	Memory
474477		Valaki2	Traffic (IOI10_traffic)	C++14	100 / 100	1222 ms	167860 KiB

traffic

#include "traffic.h"

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

#define pb push_back

const int maxn = 1e6;

struct edge {
    int to, id, cong;
    edge(int to_, int id_, int cong_) : to(to_), id(id_), cong(cong_) {}
};

int n, sum;
vector<edge> g[maxn + 1];
int val[maxn + 1];
bool vis[maxn + 1];

int dfs(int x, int id) {
    vis[x] = true;
    int res = val[x];
    int cur_ind = 0;
    for(int i = 0; i < g[x].size(); ++i) {
        if(g[x][i].id == id) {
            cur_ind = i;
        } else {
            int temp = dfs(g[x][i].to, g[x][i].id);
            res += temp;
            g[x][i].cong = temp;
        }
    }
    if(x != 1) g[x][cur_ind].cong = sum - res;
    return res;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    n = N;
    for(int i = 0; i < n; ++i) {
        val[i + 1] = pp[i];
        sum += val[i + 1];
    }
    for(int i = 0; i < n - 1; ++i) {
        g[S[i] + 1].pb(edge(D[i] + 1, i + 1, 0));
        g[D[i] + 1].pb(edge(S[i] + 1, i + 1, 0));
    }
    dfs(1, 0);
    /*for(int i = 1; i <= n; ++i) {
        cout << i << ": " << val[i] << ";\n";
        for(edge x : g[i]) cout << x.to << " " << x.id << " " << x.cong << "\n";
        cout << "\n";
    }*/
    int ans = 1, best = INT_MAX;
    for(int i = 1; i <= n; ++i) {
        int cur = 0;
        for(edge e : g[i]) {
            cur = max(cur, e.cong);
        }
        if(cur < best) {
            best = cur;
            ans = i;
        }
    }
    return ans - 1;
}

Compilation message (stderr)

traffic.cpp: In function 'int dfs(int, int)':
traffic.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i < g[x].size(); ++i) {
      |                    ~~^~~~~~~~~~~~~

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