oj.uz

Submission #783745

# Submission time Handle Problem Language Result Execution time Memory
783745 2023-07-15T09:39:51 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 208 ms 24740 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], 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)/2;
        FOR(i,l,mid+1) w[i] = 1;
        int val = ask(w);
        if (val == ans) l = mid+1;
        else r = 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;
    // && max(e[tour[i].S].x,e[tour[i].S].y) == 12
    int l = -1, r = tour.size()-1;
    // FOR(i,0,(tour.size())) {
    //     if (min(e[tour[i].S].x,e[tour[i].S].y) == 10) {
    //         cout << "NYAHAAH " << i << " " << e[tour[i].S].x << " " << e[tour[i].S].y << ln;
    //     }
    // }
    // cout << "intree4 " << intree[1] << ln;
    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;
        // cout << "l r: " << l << " " << mid << " " << r << ln;
        // cout << "w[1]: " << w[1] << ln;
        int val = ask(w);
        // cout << val;
        if (val == ans) r = mid-1;
        else {
            // if (mid == 13 && r == 13) cout << "NYEHEHEHE " << e[tour[11].S].x << " " << e[tour[11].S].y << ln;
            l = mid;
        }
    }
    // cout << "s l tour[l]: " << s << " " << l << " " << tour[l].S << 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]+1LL < 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};
            }
        }
    }
    sort(ALL(tour));
    FORX(u,tour) {
        // if (u.S == 1) cout << "OMGBRUH\n";
        intree[u.S] = 1;
    }
    // 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);
    // cout << ans << ln;
    int edge = find_edge(0);
    // cout << "x y: " << e[edge].x << " " << e[edge].y << 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;
    // cout << xs << ln;
    // if (s == xs) while (true) int bruh = 0;
    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 3 ms 6428 KB Output is correct
2 Correct 4 ms 6352 KB Output is correct
3 Correct 3 ms 6352 KB Output is correct
4 Correct 3 ms 6352 KB Output is correct
5 Correct 3 ms 6352 KB Output is correct
6 Correct 3 ms 6352 KB Output is correct
7 Correct 3 ms 6352 KB Output is correct
8 Correct 3 ms 6352 KB Output is correct
9 Correct 3 ms 6428 KB Output is correct
10 Correct 3 ms 6424 KB Output is correct
11 Correct 3 ms 6420 KB Output is correct
12 Correct 3 ms 6352 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Output is correct
2 Correct 13 ms 7952 KB Output is correct
3 Correct 132 ms 20848 KB Output is correct
4 Correct 102 ms 20840 KB Output is correct
5 Correct 115 ms 20912 KB Output is correct
6 Correct 145 ms 20848 KB Output is correct
7 Correct 139 ms 20812 KB Output is correct
8 Correct 136 ms 20856 KB Output is correct
9 Correct 129 ms 20840 KB Output is correct
10 Correct 104 ms 20832 KB Output is correct
11 Correct 134 ms 20960 KB Output is correct
12 Correct 125 ms 20936 KB Output is correct
13 Correct 96 ms 20840 KB Output is correct
14 Correct 130 ms 20916 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7952 KB Output is correct
2 Correct 19 ms 9556 KB Output is correct
3 Correct 38 ms 10784 KB Output is correct
4 Correct 86 ms 20364 KB Output is correct
5 Correct 105 ms 20416 KB Output is correct
6 Correct 90 ms 20328 KB Output is correct
7 Correct 81 ms 20320 KB Output is correct
8 Correct 112 ms 20440 KB Output is correct
9 Correct 79 ms 20444 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 12 ms 8060 KB Output is correct
3 Correct 87 ms 18248 KB Output is correct
4 Correct 121 ms 20840 KB Output is correct
5 Correct 110 ms 20844 KB Output is correct
6 Correct 137 ms 20848 KB Output is correct
7 Correct 148 ms 20836 KB Output is correct
8 Correct 105 ms 20936 KB Output is correct
9 Correct 136 ms 20852 KB Output is correct
10 Correct 125 ms 20852 KB Output is correct
11 Correct 149 ms 20852 KB Output is correct
12 Correct 105 ms 20920 KB Output is correct
13 Correct 154 ms 20892 KB Output is correct
14 Correct 137 ms 20828 KB Output is correct
15 Correct 102 ms 20836 KB Output is correct
16 Correct 106 ms 20848 KB Output is correct
17 Correct 147 ms 20916 KB Output is correct
18 Correct 142 ms 20840 KB Output is correct
19 Correct 157 ms 20844 KB Output is correct
20 Correct 129 ms 20948 KB Output is correct
21 Correct 91 ms 20428 KB Output is correct
22 Correct 89 ms 20516 KB Output is correct
23 Correct 129 ms 20452 KB Output is correct
24 Correct 115 ms 20424 KB Output is correct
25 Correct 127 ms 20972 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8052 KB Output is correct
2 Correct 17 ms 8144 KB Output is correct
3 Correct 161 ms 21800 KB Output is correct
4 Correct 129 ms 22792 KB Output is correct
5 Correct 187 ms 24740 KB Output is correct
6 Incorrect 208 ms 24724 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 13 ms 8076 KB Output is correct
2 Correct 15 ms 8272 KB Output is correct
3 Partially correct 175 ms 21976 KB Output is partially correct
4 Incorrect 148 ms 22300 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -