oj.uz

Submission #783742

# Submission time Handle Problem Language Result Execution time Memory
783742 2023-07-15T09:36:15 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 160 ms 20972 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,mid,r+1) w[i] = 1;
        int val = ask(w);
        if (val == ans) r = mid;
        else l = mid+1;
    }
    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 6372 KB Output is correct
2 Correct 3 ms 6352 KB Output is correct
3 Correct 3 ms 6420 KB Output is correct
4 Correct 3 ms 6352 KB Output is correct
5 Correct 3 ms 6360 KB Output is correct
6 Correct 3 ms 6428 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 6352 KB Output is correct
10 Correct 3 ms 6352 KB Output is correct
11 Correct 3 ms 6420 KB Output is correct
12 Correct 3 ms 6420 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6668 KB Output is correct
2 Correct 15 ms 7952 KB Output is correct
3 Correct 147 ms 20844 KB Output is correct
4 Correct 133 ms 20892 KB Output is correct
5 Correct 119 ms 20832 KB Output is correct
6 Correct 113 ms 20808 KB Output is correct
7 Correct 123 ms 20812 KB Output is correct
8 Correct 150 ms 20876 KB Output is correct
9 Correct 121 ms 20832 KB Output is correct
10 Correct 129 ms 20840 KB Output is correct
11 Correct 121 ms 20856 KB Output is correct
12 Correct 102 ms 20892 KB Output is correct
13 Correct 97 ms 20884 KB Output is correct
14 Correct 111 ms 20820 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7948 KB Output is correct
2 Correct 27 ms 9600 KB Output is correct
3 Correct 34 ms 10924 KB Output is correct
4 Correct 82 ms 20440 KB Output is correct
5 Correct 115 ms 20420 KB Output is correct
6 Correct 95 ms 20416 KB Output is correct
7 Correct 100 ms 20332 KB Output is correct
8 Correct 87 ms 20316 KB Output is correct
9 Correct 77 ms 20448 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 7948 KB Output is correct
3 Correct 97 ms 18164 KB Output is correct
4 Correct 113 ms 20836 KB Output is correct
5 Correct 146 ms 20836 KB Output is correct
6 Correct 146 ms 20836 KB Output is correct
7 Correct 135 ms 20844 KB Output is correct
8 Correct 107 ms 20828 KB Output is correct
9 Correct 136 ms 20840 KB Output is correct
10 Correct 120 ms 20848 KB Output is correct
11 Correct 124 ms 20908 KB Output is correct
12 Correct 110 ms 20844 KB Output is correct
13 Correct 109 ms 20832 KB Output is correct
14 Correct 107 ms 20924 KB Output is correct
15 Correct 123 ms 20844 KB Output is correct
16 Correct 104 ms 20972 KB Output is correct
17 Correct 126 ms 20916 KB Output is correct
18 Correct 148 ms 20916 KB Output is correct
19 Correct 110 ms 20844 KB Output is correct
20 Correct 160 ms 20824 KB Output is correct
21 Correct 97 ms 20420 KB Output is correct
22 Correct 96 ms 20360 KB Output is correct
23 Correct 145 ms 20448 KB Output is correct
24 Correct 133 ms 20384 KB Output is correct
25 Correct 114 ms 20820 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 8076 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 8068 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -