oj.uz

Submission #783626

# Submission time Handle Problem Language Result Execution time Memory
783626 2023-07-15T06:43:59 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 193 ms 33420 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) {
    // tour.clear();
    // dfs(s,pa,vec);
    // FORX(u,tour) cout << u << " ";
    // cout << ln;
    int l = -1, r = m-1;
    // FOR(i,0,m) cout << intree[i] << " ";
    // cout << ln;
    while (l < r) {
        FOR(i,0,m) w[i] = 0;
        int mid = (l+r+1)/2;
        FOR(i,mid,r+1) w[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 : l;
}

int find_edge1(int s, int pa, int idx, vector<PII> vec[]) {
    tour.clear();
    dfs(s,pa,vec);
    // FORX(u,tour) cout << u << " ";
    // cout << ln;
    
    // FOR(i,0,m) cout << intree[i] << " ";
    // cout << ln;
    int l = -1, r = tour.size()-1;
    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 idx, 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.S != -1) {
                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);
    int xs = e[edge].x, ys = e[edge].y;
    // cout << "xs ys: " << xs << " " << ys << ln;
    bfs_tree(xs,edge,v,v1);
    // FOR(i,0,n) {
    //     cout << i << ": ";
    //     FORX(u,v2[i]) cout << u.F << " ";
    //     cout << ln;
    // }
    // return;
    int edge1 = find_edge1(xs,ys,edge,v1);
    bfs_tree(ys,edge,v,v1);
    int edge2 = find_edge1(ys,xs,edge,v1);
    int32_t S = edge1 == -1 ? xs : e[edge1].y, T = edge2 == -1 ? ys : e[edge2].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 9476 KB Output is correct
2 Correct 6 ms 9472 KB Output is correct
3 Correct 5 ms 9496 KB Output is correct
4 Correct 5 ms 9424 KB Output is correct
5 Correct 6 ms 9472 KB Output is correct
6 Correct 4 ms 9448 KB Output is correct
7 Correct 5 ms 9472 KB Output is correct
8 Correct 5 ms 9480 KB Output is correct
9 Correct 5 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 5 ms 9424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9564 KB Output is correct
2 Correct 17 ms 11248 KB Output is correct
3 Correct 140 ms 26200 KB Output is correct
4 Correct 122 ms 24880 KB Output is correct
5 Correct 102 ms 24936 KB Output is correct
6 Correct 125 ms 26216 KB Output is correct
7 Correct 130 ms 24896 KB Output is correct
8 Correct 124 ms 26224 KB Output is correct
9 Correct 149 ms 26184 KB Output is correct
10 Correct 103 ms 26204 KB Output is correct
11 Correct 168 ms 28284 KB Output is correct
12 Correct 153 ms 29056 KB Output is correct
13 Correct 137 ms 28376 KB Output is correct
14 Correct 140 ms 28672 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12028 KB Output is correct
2 Correct 20 ms 14096 KB Output is correct
3 Correct 37 ms 17080 KB Output is correct
4 Correct 81 ms 30140 KB Output is correct
5 Correct 109 ms 30616 KB Output is correct
6 Correct 103 ms 32508 KB Output is correct
7 Correct 91 ms 33356 KB Output is correct
8 Correct 113 ms 30924 KB Output is correct
9 Correct 83 ms 31876 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9552 KB Output is correct
2 Correct 15 ms 11256 KB Output is correct
3 Correct 117 ms 21492 KB Output is correct
4 Correct 123 ms 26216 KB Output is correct
5 Correct 146 ms 26208 KB Output is correct
6 Correct 111 ms 26248 KB Output is correct
7 Correct 122 ms 26092 KB Output is correct
8 Correct 125 ms 26064 KB Output is correct
9 Correct 126 ms 26220 KB Output is correct
10 Correct 102 ms 26100 KB Output is correct
11 Correct 130 ms 28000 KB Output is correct
12 Correct 131 ms 28924 KB Output is correct
13 Correct 126 ms 28420 KB Output is correct
14 Correct 157 ms 28700 KB Output is correct
15 Correct 99 ms 24896 KB Output is correct
16 Correct 144 ms 24892 KB Output is correct
17 Correct 131 ms 28376 KB Output is correct
18 Correct 129 ms 28596 KB Output is correct
19 Correct 145 ms 26156 KB Output is correct
20 Correct 150 ms 29500 KB Output is correct
21 Correct 101 ms 24772 KB Output is correct
22 Correct 96 ms 25700 KB Output is correct
23 Correct 110 ms 25792 KB Output is correct
24 Correct 131 ms 25200 KB Output is correct
25 Correct 135 ms 33420 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11436 KB Output is correct
2 Correct 16 ms 11460 KB Output is correct
3 Correct 174 ms 27084 KB Output is correct
4 Correct 128 ms 26744 KB Output is correct
5 Correct 193 ms 29720 KB Output is correct
6 Incorrect 187 ms 29728 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11404 KB Output is correct
2 Correct 18 ms 11484 KB Output is correct
3 Correct 172 ms 27092 KB Output is correct
4 Partially correct 171 ms 27544 KB Output is partially correct
5 Incorrect 193 ms 27996 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -