oj.uz

Submission #783664

# Submission time Handle Problem Language Result Execution time Memory
783664 2023-07-15T07:59:29 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 180 ms 27892 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], tour;
vector<int32_t> w;
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 idx, vector<PII> vec[]) {
    // tour.clear();
    // dfs(s,pa,vec);
    // FORX(u,tour) cout << u.S << " ";
    // 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];
        int mid = (l+r+1)/2;
        FOR(i,mid,r+1) w[tour[i].S] = 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].S;
}

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;
    tour.clear();
    queue<int> q;
    q.push(start);
    vector<int> d(n,INF);
    vector<PII> p(n,{-1,-1});
    d[start] = 0LL;
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        // cout << s << " ";
        FORX(u,vec[s]) {
            if (d[u.F] == INF) {
                d[u.F] = d[s]+1LL;
                tour.PB({d[u.F],u.S});
                if (e[u.S].y != u.F) swap(e[u.S].x, e[u.S].y);
                q.push(u.F);
                // p[u.F] = {s,u.S};
            }
        }
    }
    FORX(u,tour) intree[u.S] = 1;
    sort(ALL(tour));
    // FOR(i,0,n) cout << p[i].F << " ";
    // cout << ln;
    // 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);
    // cout << edge << ln;
    int xs = e[edge].x;
    // cout << "xs ys: " << xs << " " << ys << ln;
    
    // FOR(i,0,n) {
    //     cout << i << ": ";
    //     FORX(u,v2[i]) cout << u.F << " ";
    //     cout << ln;
    // }
    // return;
    bfs_tree(xs,edge,v,v1);
    int edge1 = find_edge1(xs,edge,v1);
    int32_t s = edge1 == -1 ? xs : e[edge1].y;
    bfs_tree(s,edge1,v,v1);
    int edge2 = find_edge1(s,edge1,v1);
    int32_t t = edge2 == -1 ? s : 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 9424 KB Output is correct
2 Correct 5 ms 9476 KB Output is correct
3 Correct 4 ms 9424 KB Output is correct
4 Correct 4 ms 9456 KB Output is correct
5 Correct 4 ms 9424 KB Output is correct
6 Correct 4 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 6 ms 9424 KB Output is correct
11 Correct 6 ms 9500 KB Output is correct
12 Correct 4 ms 9424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9560 KB Output is correct
2 Correct 14 ms 11028 KB Output is correct
3 Correct 108 ms 23904 KB Output is correct
4 Correct 125 ms 23920 KB Output is correct
5 Correct 127 ms 23952 KB Output is correct
6 Correct 126 ms 23892 KB Output is correct
7 Correct 131 ms 23956 KB Output is correct
8 Correct 119 ms 23892 KB Output is correct
9 Correct 130 ms 23892 KB Output is correct
10 Correct 98 ms 23904 KB Output is correct
11 Correct 99 ms 23876 KB Output is correct
12 Correct 101 ms 24064 KB Output is correct
13 Correct 100 ms 23884 KB Output is correct
14 Correct 99 ms 23968 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11020 KB Output is correct
2 Correct 25 ms 12568 KB Output is correct
3 Correct 34 ms 13828 KB Output is correct
4 Correct 110 ms 23488 KB Output is correct
5 Correct 86 ms 23364 KB Output is correct
6 Correct 89 ms 23460 KB Output is correct
7 Correct 104 ms 23420 KB Output is correct
8 Correct 72 ms 23496 KB Output is correct
9 Correct 95 ms 23412 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9560 KB Output is correct
2 Correct 16 ms 11008 KB Output is correct
3 Correct 103 ms 21208 KB Output is correct
4 Correct 137 ms 23888 KB Output is correct
5 Correct 105 ms 23908 KB Output is correct
6 Correct 123 ms 23892 KB Output is correct
7 Correct 136 ms 23884 KB Output is correct
8 Correct 126 ms 23876 KB Output is correct
9 Correct 112 ms 23900 KB Output is correct
10 Correct 129 ms 23912 KB Output is correct
11 Correct 130 ms 23956 KB Output is correct
12 Correct 140 ms 23908 KB Output is correct
13 Correct 127 ms 23964 KB Output is correct
14 Correct 122 ms 23956 KB Output is correct
15 Correct 121 ms 23996 KB Output is correct
16 Correct 138 ms 23944 KB Output is correct
17 Correct 115 ms 23964 KB Output is correct
18 Correct 109 ms 23948 KB Output is correct
19 Correct 122 ms 23880 KB Output is correct
20 Correct 99 ms 23940 KB Output is correct
21 Correct 108 ms 23408 KB Output is correct
22 Correct 105 ms 23476 KB Output is correct
23 Correct 105 ms 23600 KB Output is correct
24 Correct 118 ms 23488 KB Output is correct
25 Correct 117 ms 23884 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 11204 KB Output is correct
2 Correct 17 ms 11276 KB Output is correct
3 Correct 132 ms 24864 KB Output is correct
4 Correct 131 ms 25840 KB Output is correct
5 Correct 180 ms 27892 KB Output is correct
6 Incorrect 167 ms 27780 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 17 ms 11096 KB Output is correct
2 Correct 20 ms 11196 KB Output is correct
3 Partially correct 153 ms 24960 KB Output is partially correct
4 Partially correct 130 ms 25352 KB Output is partially correct
5 Incorrect 132 ms 25904 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -