oj.uz

답안 #612034

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
612034 2022-07-29T10:19:53 Z hibiki 통행료 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 164 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -