Submission #612034

#	Time	Username	Problem	Language	Result	Execution time	Memory
612034		hibiki	통행료 (IOI18_highway)	C++11	12 / 100	187 ms	262144 KiB

highway

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

#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

int n, m;
long long a, b, ret;
bool use[130005], fi = true;
vector<int> st, u, v, ed[100005];
set<int> pos;

int dfs(int nw, int fa, long long sum, long long tar)
{
    if (fi && sum == tar)
    {
        pos.insert(nw);
        return 1;
    }
    if (sum == tar && pos.find(nw) != pos.end())
        return 1;
    if (pos.find(nw) != pos.end())
        pos.erase(nw);
    int g[2] = {0, 0};
    vector<pair<int, int>> c;
    for (auto _ : ed[nw])
    {
        int go = u[_] ^ v[_] ^ nw;

        if (go == fa || !use[_])
            continue;

        ret = dfs(go, nw, sum + ((st[_] == 0) ? a : b), tar);
        if (ret)
            c.pb({ret, _});
        else
            use[_] = false;
    }
    sort(all(c));
    for (int i = sz(c) - 1; i >= 0; i--)
    {
        if (g[0] > g[1])
        {
            g[1] += c[i].f;
            st[c[i].s] = 1;
        }
        else
        {
            g[0] += c[i].f;
            st[c[i].s] = 0;
        }
    }
    return g[0] + g[1];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    m = sz(U);
    n = N, u = U, v = V, a = A, b = B;
    for (int i = 0; i < m; i++)
    {
        ed[u[i]].pb(i);
        ed[v[i]].pb(i);
        use[i] = true;
    }

    st = vector<int>(m, 0);
    while (1)
    {
        ret = ask(st);
        ret = dfs(0, 0, 0ll, ret);
        if (ret == 1ll)
        {
            answer(0, *pos.begin());
            return;
        }
        fi = false;
    }

    answer(0, n - 1);
}

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