oj.uz

Submission #783613

# Submission time Handle Problem Language Result Execution time Memory
783613 2023-07-15T06:21:38 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 172 ms 37512 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int64_t(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], v2[MAXN];
vector<int32_t> w, tour;
vector<Edge> e;
int d[MAXN], ans;
bool intree[MAXN];

void dfs(int s, int pa, vector<PII> vec[]) {
    FORX(u,vec[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,vec);
    }
}

int find_edge(int s, int pa, int idx, vector<PII> vec[]) {
    tour.clear();
    dfs(s,pa,vec);
    // FORX(u,tour) cout << u << " ";
    // cout << ln;
    int l = -1, r = tour.size()-1;
    // FOR(i,0,m) cout << intree[i] << " ";
    // cout << ln;
    while (l < r) {
        FOR(i,0,m) w[i] = !intree[i] && i != idx;
        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 << " " << tour[l] << ln;
    return l == -1 ? -1 : tour[l];
}

void bfs_tree(int start, int pa, vector<PII> vec[], vector<PII> vec1[]) {
    FOR(i,0,n) vec1[i].clear();
    FOR(i,0,m) intree[i] = 0;
    queue<int> q;
    q.push(start);
    vector<int> d(n,INF);
    vector<PII> p(n,{-1,-1});
    d[start] = 0;
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        // cout << s << " ";
        FORX(u,vec[s]) {
            if (d[s]+1 < d[u.F] && u.F != pa) {
                d[u.F] = d[s]+1;
                q.push(u.F);
                p[u.F] = {s,u.S};
            }
        }
    }
    // cout << ln;
    FOR(i,0,n) {
        if (p[i].F != -1) {
            vec1[p[i].F].PB({i,p[i].S});
            vec1[i].PB(p[i]);
            intree[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,v,v1);
    // FOR(i,0,m) cout << intree[i] << " ";
    // cout << ln;
    FOR(i,0,m) w.PB(0);
    ans = ask(w);
    int edge = find_edge(0,-1,-1,v1);
    int xs = e[edge].x, ys = e[edge].y;
    // cout << "xs ys: " << xs << " " << ys << ln;
    bfs_tree(xs,ys,v1,v2);
    // FOR(i,0,n) {
    //     cout << i << ": ";
    //     FORX(u,v2[i]) cout << u.F << " ";
    //     cout << ln;
    // }
    // return;
    int edge1 = find_edge(xs,ys,edge,v2);
    int32_t S = ys, T = edge1 == -1 ? xs : e[edge1].y;
    // cout << "S T: " << S << " " << T << ln;
    answer(S,T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9424 KB Output is correct
2 Correct 5 ms 9488 KB Output is correct
3 Correct 5 ms 9424 KB Output is correct
4 Correct 5 ms 9424 KB Output is correct
5 Correct 4 ms 9424 KB Output is correct
6 Correct 4 ms 9452 KB Output is correct
7 Correct 5 ms 9360 KB Output is correct
8 Correct 5 ms 9424 KB Output is correct
9 Correct 4 ms 9424 KB Output is correct
10 Correct 4 ms 9424 KB Output is correct
11 Correct 4 ms 9424 KB Output is correct
12 Correct 4 ms 9480 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 16 ms 11676 KB Output is correct
3 Correct 172 ms 30108 KB Output is correct
4 Correct 119 ms 30120 KB Output is correct
5 Correct 143 ms 30084 KB Output is correct
6 Correct 132 ms 30100 KB Output is correct
7 Correct 116 ms 30076 KB Output is correct
8 Correct 140 ms 30084 KB Output is correct
9 Correct 149 ms 30136 KB Output is correct
10 Correct 128 ms 30104 KB Output is correct
11 Correct 144 ms 29380 KB Output is correct
12 Correct 134 ms 33020 KB Output is correct
13 Correct 154 ms 32332 KB Output is correct
14 Correct 168 ms 32484 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12128 KB Output is correct
2 Correct 26 ms 15032 KB Output is correct
3 Correct 42 ms 18472 KB Output is correct
4 Correct 128 ms 35652 KB Output is correct
5 Correct 119 ms 34784 KB Output is correct
6 Correct 107 ms 36684 KB Output is correct
7 Correct 110 ms 37132 KB Output is correct
8 Correct 118 ms 35908 KB Output is correct
9 Correct 101 ms 36360 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9636 KB Output is correct
2 Correct 15 ms 11768 KB Output is correct
3 Correct 110 ms 25476 KB Output is correct
4 Correct 130 ms 30072 KB Output is correct
5 Correct 117 ms 30172 KB Output is correct
6 Correct 108 ms 30080 KB Output is correct
7 Correct 149 ms 30092 KB Output is correct
8 Correct 154 ms 30068 KB Output is correct
9 Correct 119 ms 30080 KB Output is correct
10 Correct 166 ms 30112 KB Output is correct
11 Correct 127 ms 31184 KB Output is correct
12 Correct 155 ms 32888 KB Output is correct
13 Correct 150 ms 31744 KB Output is correct
14 Correct 161 ms 32676 KB Output is correct
15 Correct 125 ms 30096 KB Output is correct
16 Correct 123 ms 30116 KB Output is correct
17 Correct 152 ms 32640 KB Output is correct
18 Correct 142 ms 32800 KB Output is correct
19 Correct 112 ms 30108 KB Output is correct
20 Correct 131 ms 33504 KB Output is correct
21 Correct 101 ms 29156 KB Output is correct
22 Correct 108 ms 29196 KB Output is correct
23 Correct 129 ms 29348 KB Output is correct
24 Correct 109 ms 30384 KB Output is correct
25 Correct 148 ms 37512 KB Output is correct

Subtask #5
0 / 18.0

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