oj.uz

Submission #783752

# Submission time Handle Problem Language Result Execution time Memory
783752 2023-07-15T09:49:04 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
90 / 100
 249 ms 24844 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) {
        
        int mid = (l+r)/2;
        FOR(i,0,m) w[i] = i <= mid;
        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 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 6352 KB Output is correct
3 Correct 5 ms 6352 KB Output is correct
4 Correct 3 ms 6420 KB Output is correct
5 Correct 3 ms 6428 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 3 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 4 ms 6480 KB Output is correct
2 Correct 12 ms 7948 KB Output is correct
3 Correct 121 ms 20844 KB Output is correct
4 Correct 122 ms 20844 KB Output is correct
5 Correct 134 ms 20852 KB Output is correct
6 Correct 108 ms 20860 KB Output is correct
7 Correct 111 ms 20848 KB Output is correct
8 Correct 156 ms 20864 KB Output is correct
9 Correct 109 ms 20844 KB Output is correct
10 Correct 144 ms 20840 KB Output is correct
11 Correct 149 ms 20832 KB Output is correct
12 Correct 112 ms 20900 KB Output is correct
13 Correct 151 ms 20848 KB Output is correct
14 Correct 151 ms 20832 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7948 KB Output is correct
2 Correct 24 ms 9568 KB Output is correct
3 Correct 27 ms 10860 KB Output is correct
4 Correct 73 ms 20440 KB Output is correct
5 Correct 109 ms 20464 KB Output is correct
6 Correct 75 ms 20396 KB Output is correct
7 Correct 78 ms 20420 KB Output is correct
8 Correct 102 ms 20520 KB Output is correct
9 Correct 101 ms 20360 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 15 ms 7952 KB Output is correct
3 Correct 80 ms 18244 KB Output is correct
4 Correct 142 ms 20844 KB Output is correct
5 Correct 117 ms 20860 KB Output is correct
6 Correct 117 ms 20896 KB Output is correct
7 Correct 103 ms 20852 KB Output is correct
8 Correct 106 ms 20828 KB Output is correct
9 Correct 126 ms 20844 KB Output is correct
10 Correct 152 ms 20864 KB Output is correct
11 Correct 147 ms 20868 KB Output is correct
12 Correct 111 ms 20940 KB Output is correct
13 Correct 109 ms 20832 KB Output is correct
14 Correct 151 ms 20900 KB Output is correct
15 Correct 149 ms 20848 KB Output is correct
16 Correct 111 ms 20852 KB Output is correct
17 Correct 112 ms 20828 KB Output is correct
18 Correct 134 ms 20964 KB Output is correct
19 Correct 136 ms 20812 KB Output is correct
20 Correct 123 ms 20836 KB Output is correct
21 Correct 119 ms 20428 KB Output is correct
22 Correct 114 ms 20336 KB Output is correct
23 Correct 109 ms 20464 KB Output is correct
24 Correct 115 ms 20408 KB Output is correct
25 Correct 143 ms 20880 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8084 KB Output is correct
2 Correct 18 ms 8140 KB Output is correct
3 Correct 155 ms 21800 KB Output is correct
4 Correct 139 ms 22796 KB Output is correct
5 Correct 173 ms 24740 KB Output is correct
6 Correct 165 ms 24736 KB Output is correct
7 Correct 167 ms 24732 KB Output is correct
8 Correct 211 ms 24728 KB Output is correct
9 Correct 152 ms 19100 KB Output is correct
10 Correct 130 ms 20028 KB Output is correct
11 Correct 119 ms 21400 KB Output is correct
12 Correct 159 ms 23912 KB Output is correct
13 Correct 154 ms 24440 KB Output is correct
14 Correct 177 ms 24732 KB Output is correct
15 Correct 156 ms 24796 KB Output is correct
16 Correct 161 ms 21496 KB Output is correct
17 Correct 91 ms 20640 KB Output is correct
18 Correct 117 ms 20912 KB Output is correct
19 Correct 100 ms 20764 KB Output is correct
20 Correct 133 ms 20840 KB Output is correct
21 Correct 201 ms 24728 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8076 KB Output is correct
2 Correct 19 ms 8160 KB Output is correct
3 Partially correct 133 ms 21900 KB Output is partially correct
4 Correct 160 ms 22308 KB Output is correct
5 Partially correct 154 ms 22792 KB Output is partially correct
6 Partially correct 201 ms 24716 KB Output is partially correct
7 Partially correct 117 ms 21920 KB Output is partially correct
8 Partially correct 145 ms 22288 KB Output is partially correct
9 Correct 138 ms 22772 KB Output is correct
10 Partially correct 191 ms 24728 KB Output is partially correct
11 Partially correct 196 ms 24724 KB Output is partially correct
12 Partially correct 179 ms 24704 KB Output is partially correct
13 Correct 168 ms 21400 KB Output is correct
14 Correct 137 ms 19900 KB Output is correct
15 Correct 121 ms 21416 KB Output is correct
16 Correct 100 ms 20024 KB Output is correct
17 Correct 120 ms 21140 KB Output is correct
18 Correct 146 ms 20008 KB Output is correct
19 Partially correct 149 ms 23936 KB Output is partially correct
20 Partially correct 191 ms 24364 KB Output is partially correct
21 Partially correct 147 ms 24720 KB Output is partially correct
22 Partially correct 201 ms 24844 KB Output is partially correct
23 Partially correct 173 ms 24752 KB Output is partially correct
24 Correct 163 ms 24736 KB Output is correct
25 Partially correct 180 ms 24816 KB Output is partially correct
26 Partially correct 150 ms 24740 KB Output is partially correct
27 Partially correct 125 ms 20768 KB Output is partially correct
28 Partially correct 97 ms 20588 KB Output is partially correct
29 Correct 105 ms 20912 KB Output is correct
30 Partially correct 127 ms 20724 KB Output is partially correct
31 Correct 143 ms 20712 KB Output is correct
32 Partially correct 94 ms 20632 KB Output is partially correct
33 Partially correct 128 ms 20852 KB Output is partially correct
34 Partially correct 92 ms 20796 KB Output is partially correct
35 Partially correct 119 ms 20620 KB Output is partially correct
36 Correct 107 ms 20480 KB Output is correct
37 Partially correct 107 ms 20968 KB Output is partially correct
38 Correct 117 ms 20996 KB Output is correct
39 Partially correct 141 ms 24844 KB Output is partially correct
40 Partially correct 249 ms 24792 KB Output is partially correct
41 Partially correct 149 ms 24788 KB Output is partially correct
42 Correct 169 ms 24720 KB Output is correct