Submission #339090

#	Time	Username	Problem	Language	Result	Execution time	Memory
339090		Victor	Traffic (IOI10_traffic)	C++17	0 / 100	21 ms	23916 KiB

traffic

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define INF 1000000000
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;

vi graph[1000005];
vii traffic;
int subs[1000005], pop[1000005], best = 2 * INF + 1, ans;
bitset<1000005> vis;

void getsubs(int u)
{
    vis[u] = 1;
    int s = 0;
    trav(v, graph[u])
    {
        if (vis[v])
            continue;
        getsubs(v);
        s += subs[v] + pop[v];
    }
    subs[u] = s;
}

void solve(int u, int over)
{
    vis[u] = 1;
    traffic.clear();

    trav(v, graph[u])
    {
        if (vis[v])
            continue;
        traffic.emplace_back(subs[v] + pop[v], v);
    }

    sort(traffic.begin(), traffic.end(), greater<>());
    if (max(traffic[0].first, over) < best) 
    {
        best = max(traffic[0].first, over);
        ans = u;
    }

    over += pop[u];
    rep(i, 1, traffic.size())
        over += traffic[i].first;

    if (graph[u].size() == 1 && vis[graph[u][0]])
        return;

    solve(traffic[0].second, over);
}

int LocateCentre(int n, int p[], int s[], int d[])
{
    fill(graph, graph + 1000000, vi());
    rep(i, 0, n) pop[i] = p[i];
    rep(i, 0, n - 1)
    {
        graph[s[i]].push_back(d[i]);
        graph[d[i]].push_back(s[i]);
    }

    vis.reset();
    getsubs(0);
    vis.reset();
    solve(0, 0);
    return ans;
}

Compilation message (stderr)

traffic.cpp: In function 'void solve(int, int)':
traffic.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i, a, b) for (int i = a; i < (b); ++i)
      |                                        ^
traffic.cpp:54:5: note: in expansion of macro 'rep'
   54 |     rep(i, 1, traffic.size())
      |     ^~~

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