oj.uz

Submission #612034

# Submission time Handle Problem Language Result Execution time Memory
612034 2022-07-29T10:19:53 Z hibiki Highway Tolls (IOI18_highway) C++11
12 / 100
 187 ms 262144 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 1 ms 2688 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 2 ms 2620 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 2 ms 2640 KB Output is correct
12 Correct 2 ms 2768 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 16 ms 3232 KB Output is correct
3 Correct 112 ms 8612 KB Output is correct
4 Correct 126 ms 8548 KB Output is correct
5 Correct 136 ms 8580 KB Output is correct
6 Correct 116 ms 8276 KB Output is correct
7 Correct 108 ms 8416 KB Output is correct
8 Correct 131 ms 8712 KB Output is correct
9 Correct 94 ms 8204 KB Output is correct
10 Correct 127 ms 8600 KB Output is correct
11 Correct 136 ms 9108 KB Output is correct
12 Correct 145 ms 12376 KB Output is correct
13 Correct 108 ms 11340 KB Output is correct
14 Correct 165 ms 10072 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3152 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2716 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 187 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -