Submission #720464

#	Time	Username	Problem	Language	Result	Execution time	Memory
720464		LittleCube	Highway Tolls (IOI18_highway)	C++14	51 / 100	185 ms	19720 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

namespace
{
    int M;
    ll D, dis[90000];
    vector<pii> E[90000];
    vector<int> tree;
    int vis[90000], sz[90000], pre[90000];
};

void dfs(int u)
{
    vis[u] = sz[u] = 1;
    for (auto [v, i] : E[u])
        if (!vis[v])
        {
            dis[v] = dis[u] + 1;
            dfs(v);
            sz[u] += sz[v];
        }
    tree.emplace_back(u);
}

int search(vector<int> v)
{
    if (v.size() == 1)
        return v[0];
    int mid = v.size() / 2;
    vector<int> l(v.begin(), v.begin() + mid), r(v.begin() + mid, v.end()), state(M, 0);
    for (auto i : l)
        for (auto [_, j] : E[i])
            state[j] = 1;
    if (ask(state) != D)
        return search(l);
    else
        return search(r);
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    ::M = U.size();
    assert(M == N - 1);
    D = ask(vector<int>(M, 0));
    for (int i = 0; i < M; i++)
        E[U[i]].emplace_back(pii(V[i], i)), E[V[i]].emplace_back(pii(U[i], i));

    int t = 30, S = -1;
    while (t--)
    {
        vector<int> cent, subt;
        vector<int> state(M, 0);
        for (int i = 0; i < N; i++)
            if (!vis[i])
            {
                tree.clear();
                dfs(i);
                int n = sz[i], c = -1;
                for (int j : tree)
                    if (n - sz[j] <= n / 2)
                    {
                        bool valid = 1;
                        for (auto [k, _] : E[j])
                            if (n / 2 < sz[k] && sz[k] <= sz[j])
                                valid = 0;
                        if (valid)
                            c = j;
                    }
                // cerr << t << ' ' << c << '\n';
                cent.emplace_back(c);
                vis[c] = 2;
                for (auto [j, k] : E[c])
                {
                    pre[j] = k;
                    subt.emplace_back(j);
                    state[k] = 1;
                }
            }
        ll nD = ask(state);
        for (int i = 0; i < N; i++)
            if (vis[i] == 1)
                vis[i] = 0;
        if (nD == D)
            continue;
        if (nD == D - A + B)
        {
            cerr << "S is centroid\n";
            S = search(cent);
            cerr << "S is " << S << '\n';
            break;
        }
        else
        {
            cerr << "S is in some subtree\n";
            int rS = search(subt);
            cerr << "root of subtree is " << rS << '\n';
            tree.clear();
            dis[rS] = 0;
            dfs(rS);
            state = vector<int>(M, 0);
            for (int i : tree)
                for (auto [j, k] : E[i])
                    if (vis[j] == 1)
                        state[k] = 1;
            ll dist = (ask(state) - D) / (B - A);
            vector<int> vD;
            for (int i : tree)
                if (dis[i] == dist)
                    vD.emplace_back(i);
            S = search(vD);
            cerr << "S is " << S << '\n';
            break;
        }
    }
    assert(t > 0);
    tree.clear();
    for (int i = 0; i < N; i++)
        vis[i] = 0;
    dis[S] = 0;
    dfs(S);
    vector<int> vD;
    for (int i : tree)
        if (dis[i] * A == D)
            vD.emplace_back(i);
    int T = search(vD);
    cerr << "T is " << T << '\n';
    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs(int)':
highway.cpp:21:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for (auto [v, i] : E[u])
      |               ^
highway.cpp: In function 'int search(std::vector<int>)':
highway.cpp:38:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for (auto [_, j] : E[i])
      |                   ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:69:35: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |                         for (auto [k, _] : E[j])
      |                                   ^
highway.cpp:78:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |                 for (auto [j, k] : E[c])
      |                           ^
highway.cpp:108:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |                 for (auto [j, k] : E[i])
      |                           ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31