oj.uz

Submission #783612

# Submission time Handle Problem Language Result Execution time Memory
783612 2023-07-15T06:13:12 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 187 ms 262144 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], 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<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,vec[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) {
            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;
    
    dfs(0,-1,v);
    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;
    // }
    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 5 ms 9424 KB Output is correct
2 Correct 5 ms 9484 KB Output is correct
3 Correct 5 ms 9424 KB Output is correct
4 Correct 5 ms 9484 KB Output is correct
5 Correct 5 ms 9408 KB Output is correct
6 Correct 6 ms 9424 KB Output is correct
7 Correct 4 ms 9424 KB Output is correct
8 Correct 4 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 9484 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 9680 KB Output is correct
2 Correct 17 ms 11616 KB Output is correct
3 Correct 145 ms 29260 KB Output is correct
4 Correct 142 ms 29228 KB Output is correct
5 Correct 165 ms 29252 KB Output is correct
6 Correct 176 ms 29228 KB Output is correct
7 Correct 150 ms 29256 KB Output is correct
8 Correct 149 ms 29228 KB Output is correct
9 Correct 137 ms 29216 KB Output is correct
10 Correct 132 ms 29260 KB Output is correct
11 Correct 150 ms 28548 KB Output is correct
12 Correct 150 ms 32148 KB Output is correct
13 Correct 169 ms 31460 KB Output is correct
14 Correct 163 ms 31616 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12036 KB Output is correct
2 Correct 23 ms 14916 KB Output is correct
3 Correct 44 ms 18196 KB Output is correct
4 Correct 136 ms 34692 KB Output is correct
5 Correct 92 ms 33856 KB Output is correct
6 Correct 90 ms 35828 KB Output is correct
7 Correct 88 ms 36228 KB Output is correct
8 Correct 105 ms 35060 KB Output is correct
9 Correct 75 ms 35512 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 16 ms 11660 KB Output is correct
3 Correct 127 ms 24952 KB Output is correct
4 Correct 134 ms 29344 KB Output is correct
5 Correct 139 ms 29240 KB Output is correct
6 Correct 114 ms 29240 KB Output is correct
7 Correct 127 ms 29324 KB Output is correct
8 Correct 154 ms 29220 KB Output is correct
9 Correct 181 ms 29256 KB Output is correct
10 Correct 146 ms 29256 KB Output is correct
11 Correct 170 ms 30356 KB Output is correct
12 Correct 160 ms 32020 KB Output is correct
13 Correct 187 ms 30900 KB Output is correct
14 Correct 155 ms 31760 KB Output is correct
15 Correct 167 ms 29264 KB Output is correct
16 Correct 121 ms 29276 KB Output is correct
17 Correct 147 ms 31648 KB Output is correct
18 Correct 170 ms 31908 KB Output is correct
19 Correct 137 ms 29340 KB Output is correct
20 Correct 169 ms 32600 KB Output is correct
21 Correct 130 ms 28468 KB Output is correct
22 Correct 135 ms 28496 KB Output is correct
23 Correct 106 ms 28628 KB Output is correct
24 Correct 112 ms 29784 KB Output is correct
25 Correct 163 ms 36572 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 173 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 152 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -