oj.uz

Submission #783760

# Submission time Handle Problem Language Result Execution time Memory
783760 2023-07-15T09:58:06 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
90 / 100
 252 ms 24836 KB 
/*

LMFAO

MESSAGE TO SUBTASK 5 TEST CASE 6:
UNLUCKYYYYYYYYYYYYYYYYYYYY TAKE THE L
LOOK AT THOSE GREEN #00FF00 PIXELS AROUND U
I KNOW IT'S PROBABLY NOT #00FF00 EXACTL BUT IT'S STILL GREEN
UNLESS YOU'RE COLOURBLIND

*/

#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) {
        int mid = (l+r+1)/2;
        FOR(i,0,m) w[i] = i >= mid;
        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;
    // && max(e[tour[i].S].x,e[tour[i].S].y) == 12
    int flowey = tour.size();
    int l = -1, r = flowey-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];
        FOR(i,0,m) w[i] = !intree[i];
        int mid = (l+r+1)/2;
        FOR(i,mid,flowey) 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 6352 KB Output is correct
2 Correct 3 ms 6420 KB Output is correct
3 Correct 3 ms 6352 KB Output is correct
4 Correct 3 ms 6352 KB Output is correct
5 Correct 4 ms 6432 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 6352 KB Output is correct
10 Correct 4 ms 6352 KB Output is correct
11 Correct 3 ms 6352 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 3 ms 6480 KB Output is correct
2 Correct 14 ms 7948 KB Output is correct
3 Correct 121 ms 20852 KB Output is correct
4 Correct 126 ms 20852 KB Output is correct
5 Correct 123 ms 20848 KB Output is correct
6 Correct 136 ms 20864 KB Output is correct
7 Correct 128 ms 20856 KB Output is correct
8 Correct 133 ms 20868 KB Output is correct
9 Correct 108 ms 20856 KB Output is correct
10 Correct 139 ms 20852 KB Output is correct
11 Correct 133 ms 20892 KB Output is correct
12 Correct 112 ms 20884 KB Output is correct
13 Correct 139 ms 20824 KB Output is correct
14 Correct 111 ms 20840 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7952 KB Output is correct
2 Correct 27 ms 9544 KB Output is correct
3 Correct 26 ms 10816 KB Output is correct
4 Correct 79 ms 20336 KB Output is correct
5 Correct 64 ms 20336 KB Output is correct
6 Correct 93 ms 20344 KB Output is correct
7 Correct 81 ms 20448 KB Output is correct
8 Correct 114 ms 20428 KB Output is correct
9 Correct 82 ms 20408 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6512 KB Output is correct
2 Correct 13 ms 7948 KB Output is correct
3 Correct 121 ms 18160 KB Output is correct
4 Correct 162 ms 20844 KB Output is correct
5 Correct 115 ms 20848 KB Output is correct
6 Correct 157 ms 20848 KB Output is correct
7 Correct 122 ms 20852 KB Output is correct
8 Correct 100 ms 20836 KB Output is correct
9 Correct 140 ms 20852 KB Output is correct
10 Correct 132 ms 20876 KB Output is correct
11 Correct 164 ms 20888 KB Output is correct
12 Correct 107 ms 20828 KB Output is correct
13 Correct 127 ms 20912 KB Output is correct
14 Correct 127 ms 21008 KB Output is correct
15 Correct 104 ms 20844 KB Output is correct
16 Correct 136 ms 20868 KB Output is correct
17 Correct 112 ms 20948 KB Output is correct
18 Correct 122 ms 20836 KB Output is correct
19 Correct 132 ms 20764 KB Output is correct
20 Correct 109 ms 20824 KB Output is correct
21 Correct 112 ms 20368 KB Output is correct
22 Correct 116 ms 20404 KB Output is correct
23 Correct 110 ms 20452 KB Output is correct
24 Correct 118 ms 20368 KB Output is correct
25 Correct 118 ms 20804 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 8028 KB Output is correct
2 Correct 17 ms 8248 KB Output is correct
3 Correct 134 ms 21816 KB Output is correct
4 Correct 151 ms 22780 KB Output is correct
5 Correct 189 ms 24724 KB Output is correct
6 Correct 161 ms 24732 KB Output is correct
7 Correct 187 ms 24728 KB Output is correct
8 Correct 151 ms 24740 KB Output is correct
9 Correct 141 ms 19044 KB Output is correct
10 Correct 122 ms 20040 KB Output is correct
11 Correct 119 ms 21404 KB Output is correct
12 Correct 185 ms 23916 KB Output is correct
13 Correct 191 ms 24320 KB Output is correct
14 Correct 171 ms 24740 KB Output is correct
15 Correct 215 ms 24732 KB Output is correct
16 Correct 171 ms 21500 KB Output is correct
17 Correct 130 ms 20636 KB Output is correct
18 Correct 101 ms 20956 KB Output is correct
19 Correct 131 ms 20676 KB Output is correct
20 Correct 119 ms 20880 KB Output is correct
21 Correct 169 ms 24828 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8168 KB Output is correct
2 Correct 13 ms 8232 KB Output is correct
3 Partially correct 125 ms 21900 KB Output is partially correct
4 Partially correct 150 ms 22292 KB Output is partially correct
5 Correct 162 ms 22792 KB Output is correct
6 Partially correct 155 ms 24724 KB Output is partially correct
7 Partially correct 131 ms 21904 KB Output is partially correct
8 Partially correct 148 ms 22312 KB Output is partially correct
9 Partially correct 181 ms 22780 KB Output is partially correct
10 Partially correct 193 ms 24724 KB Output is partially correct
11 Partially correct 198 ms 24712 KB Output is partially correct
12 Partially correct 141 ms 24732 KB Output is partially correct
13 Correct 138 ms 21400 KB Output is correct
14 Correct 148 ms 19888 KB Output is correct
15 Correct 153 ms 21408 KB Output is correct
16 Correct 136 ms 20024 KB Output is correct
17 Correct 167 ms 21128 KB Output is correct
18 Correct 139 ms 19888 KB Output is correct
19 Partially correct 200 ms 23936 KB Output is partially correct
20 Partially correct 158 ms 24352 KB Output is partially correct
21 Partially correct 189 ms 24736 KB Output is partially correct
22 Partially correct 252 ms 24712 KB Output is partially correct
23 Partially correct 200 ms 24740 KB Output is partially correct
24 Correct 202 ms 24724 KB Output is correct
25 Partially correct 190 ms 24748 KB Output is partially correct
26 Partially correct 171 ms 24736 KB Output is partially correct
27 Correct 113 ms 20788 KB Output is correct
28 Correct 112 ms 20644 KB Output is correct
29 Correct 103 ms 20936 KB Output is correct
30 Partially correct 98 ms 20800 KB Output is partially correct
31 Correct 105 ms 20716 KB Output is correct
32 Partially correct 110 ms 20540 KB Output is partially correct
33 Partially correct 118 ms 20820 KB Output is partially correct
34 Correct 90 ms 20872 KB Output is correct
35 Partially correct 116 ms 20712 KB Output is partially correct
36 Correct 98 ms 20548 KB Output is correct
37 Partially correct 107 ms 21032 KB Output is partially correct
38 Correct 110 ms 20952 KB Output is correct
39 Partially correct 136 ms 24836 KB Output is partially correct
40 Partially correct 190 ms 24788 KB Output is partially correct
41 Partially correct 183 ms 24756 KB Output is partially correct
42 Partially correct 145 ms 24696 KB Output is partially correct