oj.uz

Submission #783609

# Submission time Handle Problem Language Result Execution time Memory
783609 2023-07-15T05:58:12 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 176 ms 28716 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
#define int long long

struct Edge {
    int x,y,depth;
};

const int MAXN = 1.3e5+5;
int n,m;
vector<PII> v[MAXN], v1[MAXN];
vector<int32_t> w, tour;
vector<Edge> e;
int d[MAXN], ans;
bool used[MAXN];

void dfs(int s, int pa) {
    FORX(u,v1[s]) {
        if (u.F == pa) continue;
        if (e[u.S].y != u.F) swap(e[u.S].x, e[u.S].y);
        tour.PB(u.S);
        dfs(u.F,s);
    }
}

int find_edge(int s, int pa) {
    tour.clear();
    dfs(s,pa);
    // FORX(u,tour) cout << u << " ";
    // cout << ln;
    int l = -1, r = tour.size()-1;
    while (l < r) {
        FOR(i,0,m) w[i] = 0;
        int mid = (l+r+1)/2;
        FOR(i,mid,r+1) w[tour[i]] = 1;
        int val = ask(w);
        if (val == ans) r = mid-1;
        else l = mid;
    }
    // cout << "s l: " << s << " " << l << ln;
    return l == -1 ? -1 : tour[l];
}

void bfs_tree(int start, int pa) {
    FOR(i,0,n) v1[i].clear();
    queue<int> q;
    q.push(start);
    vector<bool> z(n,0);
    vector<PII> p(n,{-1,-1});
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        if (z[s]) continue;
        z[s] = 1;
        FORX(u,v[s]) {
            if (!z[u.F] && u.F != pa) {
                q.push(u.F);
                p[u.F] = {s,u.S};
            }
        }
    }
    FOR(i,0,n) {
        if (p[i].F != -1) {
            v1[p[i].F].PB({i,p[i].S});
            v1[i].PB(p[i]);
            used[p[i].S] = 1;
        }
    }
}

void find_pair(int32_t N, std::vector<int32_t> U, std::vector<int32_t> V, int32_t A, int32_t B) {
    n = N; m = U.size();
    FOR(i,0,m) {
        v[U[i]].PB({V[i],i});
        v[V[i]].PB({U[i],i});
        e.PB({U[i],V[i],-1LL});
    }
    bfs_tree(0,-1);
    // FOR(i,0,n) {
    //     cout << i << ": ";
    //     FORX(u,v1[i]) cout << u.F << " ";
    //     cout << ln;
    // }
    dfs(0,-1);
    FOR(i,0,m) w.PB(0);
    ans = ask(w);
    // int l = 0, r = m-1;
    // while (l < r) {
    //     FOR(i,0,n) w[i] = 0;
    //     int mid = (l+r+1)/2;
    //     FOR(i,mid,r+1) w[tour[i]] = 1;
    //     int val = ask(w);
    //     // cout << "m a: " << mid << " " << val << ln;
    //     if (val == ans) r = mid-1;
    //     else l = mid;
    // }
    int edge = find_edge(0,-1);
    int xs = e[edge].x, ys = e[edge].y;
    // cout << "xs ys: " << xs << " " << ys << ln;
    bfs_tree(xs,ys);
    edge = find_edge(xs,ys);
    int32_t S = ys, T = edge == -1 ? xs : e[edge].y;
    // cout << "S T: " << S << " " << T << ln;
    answer(S,T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6352 KB Output is correct
2 Correct 3 ms 6432 KB Output is correct
3 Correct 3 ms 6432 KB Output is correct
4 Correct 3 ms 6352 KB Output is correct
5 Correct 4 ms 6352 KB Output is correct
6 Correct 3 ms 6416 KB Output is correct
7 Correct 3 ms 6352 KB Output is correct
8 Correct 3 ms 6432 KB Output is correct
9 Correct 3 ms 6456 KB Output is correct
10 Correct 3 ms 6352 KB Output is correct
11 Correct 3 ms 6352 KB Output is correct
12 Correct 3 ms 6352 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 11 ms 8068 KB Output is correct
3 Correct 149 ms 22420 KB Output is correct
4 Correct 145 ms 22456 KB Output is correct
5 Correct 139 ms 22468 KB Output is correct
6 Correct 114 ms 22480 KB Output is correct
7 Correct 133 ms 22468 KB Output is correct
8 Correct 144 ms 22468 KB Output is correct
9 Correct 147 ms 22460 KB Output is correct
10 Correct 116 ms 22492 KB Output is correct
11 Correct 157 ms 24232 KB Output is correct
12 Correct 146 ms 25244 KB Output is correct
13 Correct 158 ms 24428 KB Output is correct
14 Correct 136 ms 24552 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8848 KB Output is correct
2 Correct 26 ms 11320 KB Output is correct
3 Correct 36 ms 13512 KB Output is correct
4 Correct 102 ms 28632 KB Output is correct
5 Correct 92 ms 28640 KB Output is correct
6 Correct 80 ms 28716 KB Output is correct
7 Correct 90 ms 28708 KB Output is correct
8 Correct 96 ms 28632 KB Output is correct
9 Correct 76 ms 28684 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 13 ms 8208 KB Output is correct
3 Correct 114 ms 18924 KB Output is correct
4 Correct 135 ms 22484 KB Output is correct
5 Correct 112 ms 22468 KB Output is correct
6 Correct 130 ms 22484 KB Output is correct
7 Correct 101 ms 22476 KB Output is correct
8 Correct 146 ms 22452 KB Output is correct
9 Correct 117 ms 22460 KB Output is correct
10 Correct 176 ms 22460 KB Output is correct
11 Correct 150 ms 23924 KB Output is correct
12 Correct 133 ms 25096 KB Output is correct
13 Correct 159 ms 24592 KB Output is correct
14 Correct 139 ms 25032 KB Output is correct
15 Correct 165 ms 22464 KB Output is correct
16 Correct 125 ms 22472 KB Output is correct
17 Correct 139 ms 24676 KB Output is correct
18 Correct 114 ms 24816 KB Output is correct
19 Correct 131 ms 22480 KB Output is correct
20 Correct 155 ms 25600 KB Output is correct
21 Correct 80 ms 21696 KB Output is correct
22 Correct 85 ms 21680 KB Output is correct
23 Correct 91 ms 21680 KB Output is correct
24 Correct 121 ms 22624 KB Output is correct
25 Correct 170 ms 28676 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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