oj.uz

Submission #783608

# Submission time Handle Problem Language Result Execution time Memory
783608 2023-07-15T05:55:49 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 167 ms 27296 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) {
    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]) {
                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);
    // 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;
    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 6352 KB Output is correct
4 Correct 3 ms 6352 KB Output is correct
5 Correct 3 ms 6352 KB Output is correct
6 Correct 3 ms 6352 KB Output is correct
7 Correct 4 ms 6480 KB Output is correct
8 Correct 3 ms 6352 KB Output is correct
9 Correct 3 ms 6352 KB Output is correct
10 Correct 3 ms 6316 KB Output is correct
11 Correct 3 ms 6432 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 15 ms 7948 KB Output is correct
3 Correct 113 ms 21072 KB Output is correct
4 Correct 112 ms 21064 KB Output is correct
5 Correct 115 ms 21060 KB Output is correct
6 Correct 121 ms 21072 KB Output is correct
7 Correct 130 ms 21056 KB Output is correct
8 Correct 104 ms 21076 KB Output is correct
9 Correct 95 ms 21052 KB Output is correct
10 Correct 124 ms 21076 KB Output is correct
11 Correct 114 ms 22936 KB Output is correct
12 Correct 113 ms 23820 KB Output is correct
13 Correct 126 ms 23056 KB Output is correct
14 Correct 124 ms 23144 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8716 KB Output is correct
2 Correct 19 ms 11028 KB Output is correct
3 Correct 35 ms 13132 KB Output is correct
4 Correct 101 ms 27296 KB Output is correct
5 Correct 85 ms 27292 KB Output is correct
6 Correct 103 ms 27244 KB Output is correct
7 Correct 112 ms 27248 KB Output is correct
8 Correct 98 ms 27244 KB Output is correct
9 Correct 99 ms 27240 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 16 ms 8060 KB Output is correct
3 Correct 79 ms 17948 KB Output is correct
4 Correct 147 ms 21064 KB Output is correct
5 Correct 98 ms 21068 KB Output is correct
6 Correct 134 ms 21044 KB Output is correct
7 Correct 137 ms 21072 KB Output is correct
8 Correct 99 ms 21040 KB Output is correct
9 Correct 120 ms 21064 KB Output is correct
10 Correct 133 ms 21072 KB Output is correct
11 Correct 146 ms 22404 KB Output is correct
12 Correct 134 ms 23672 KB Output is correct
13 Correct 113 ms 23128 KB Output is correct
14 Correct 140 ms 23632 KB Output is correct
15 Correct 165 ms 21072 KB Output is correct
16 Correct 101 ms 21092 KB Output is correct
17 Correct 139 ms 23284 KB Output is correct
18 Correct 130 ms 23404 KB Output is correct
19 Correct 115 ms 21080 KB Output is correct
20 Correct 134 ms 24188 KB Output is correct
21 Correct 78 ms 20200 KB Output is correct
22 Correct 73 ms 20192 KB Output is correct
23 Correct 103 ms 20284 KB Output is correct
24 Correct 106 ms 21236 KB Output is correct
25 Correct 167 ms 27264 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 8076 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 16 ms 8152 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -