oj.uz

Submission #783696

# Submission time Handle Problem Language Result Execution time Memory
783696 2023-07-15T08:38:41 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 196 ms 27784 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) {
    int l = 0, r = m-1;
    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;
    }
    return 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(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});
    vector<bool> z(n,0);
    d[start] = 0LL;
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        if (z[s]) continue;
        z[s] = 1;
        // cout << s << " ";
        FORX(u,vec[s]) {
            if (d[s]+1 < d[u.F]) {
                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(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(xs,edge,v,v1);
    int edge1 = find_edge1(xs,edge,v1);
    int s = edge1 == -1 ? xs : e[edge1].y;
    bfs(s,edge1,v,v1);
    int edge2 = find_edge1(s,edge1,v1);
    int t = edge2 == -1 ? s : e[edge2].y;
    // cout << "S T: " << s << " " << t << ln;
    FOR(i,0,m) w[i] = 0;
    answer(s,t);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9396 KB Output is correct
2 Correct 4 ms 9424 KB Output is correct
3 Correct 5 ms 9472 KB Output is correct
4 Correct 4 ms 9472 KB Output is correct
5 Correct 5 ms 9424 KB Output is correct
6 Correct 4 ms 9424 KB Output is correct
7 Correct 5 ms 9472 KB Output is correct
8 Correct 5 ms 9456 KB Output is correct
9 Correct 4 ms 9480 KB Output is correct
10 Correct 5 ms 9424 KB Output is correct
11 Correct 4 ms 9424 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 9552 KB Output is correct
2 Correct 13 ms 11004 KB Output is correct
3 Correct 122 ms 23896 KB Output is correct
4 Correct 145 ms 23928 KB Output is correct
5 Correct 144 ms 23900 KB Output is correct
6 Correct 144 ms 23892 KB Output is correct
7 Correct 120 ms 23920 KB Output is correct
8 Correct 129 ms 23872 KB Output is correct
9 Correct 101 ms 23900 KB Output is correct
10 Correct 140 ms 23908 KB Output is correct
11 Correct 123 ms 23924 KB Output is correct
12 Correct 106 ms 23868 KB Output is correct
13 Correct 109 ms 23968 KB Output is correct
14 Correct 114 ms 23968 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11020 KB Output is correct
2 Correct 25 ms 12548 KB Output is correct
3 Correct 41 ms 13952 KB Output is correct
4 Correct 102 ms 23488 KB Output is correct
5 Correct 117 ms 23492 KB Output is correct
6 Correct 99 ms 23464 KB Output is correct
7 Correct 117 ms 23368 KB Output is correct
8 Correct 98 ms 23492 KB Output is correct
9 Correct 76 ms 23372 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9564 KB Output is correct
2 Correct 18 ms 11040 KB Output is correct
3 Correct 92 ms 21212 KB Output is correct
4 Correct 143 ms 23852 KB Output is correct
5 Correct 137 ms 23904 KB Output is correct
6 Correct 129 ms 23900 KB Output is correct
7 Correct 148 ms 23888 KB Output is correct
8 Correct 99 ms 23876 KB Output is correct
9 Correct 122 ms 23896 KB Output is correct
10 Correct 106 ms 23912 KB Output is correct
11 Correct 139 ms 23872 KB Output is correct
12 Correct 138 ms 23972 KB Output is correct
13 Correct 155 ms 23972 KB Output is correct
14 Correct 130 ms 23944 KB Output is correct
15 Correct 112 ms 23924 KB Output is correct
16 Correct 136 ms 23904 KB Output is correct
17 Correct 140 ms 23968 KB Output is correct
18 Correct 115 ms 23924 KB Output is correct
19 Correct 136 ms 23880 KB Output is correct
20 Correct 116 ms 24112 KB Output is correct
21 Correct 99 ms 23464 KB Output is correct
22 Correct 83 ms 23472 KB Output is correct
23 Correct 102 ms 23476 KB Output is correct
24 Correct 90 ms 23464 KB Output is correct
25 Correct 131 ms 23872 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11088 KB Output is correct
2 Correct 18 ms 11200 KB Output is correct
3 Correct 151 ms 24904 KB Output is correct
4 Correct 157 ms 25852 KB Output is correct
5 Correct 161 ms 27784 KB Output is correct
6 Incorrect 196 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 11148 KB Output is correct
2 Correct 21 ms 11172 KB Output is correct
3 Partially correct 144 ms 24956 KB Output is partially correct
4 Partially correct 173 ms 25424 KB Output is partially correct
5 Incorrect 162 ms 25840 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -