oj.uz

Submission #783819

# Submission time Handle Problem Language Result Execution time Memory
783819 2023-07-15T10:55:06 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 211 ms 22992 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], tour;
vector<int32_t> w;
vector<Edge> e;
int dist[2][MAXN], eist[2][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);
//     }
// }

void pre_bfs(int start, int idx) {
    FOR(i,0,n) dist[idx][i] = INF;
    dist[idx][start] = 0;
    queue<int> q;
    q.push(start);
    vector<bool> z(n,0);
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        if (z[s]) continue;
        z[s] = 1;
        FORX(u,v[s]) {
            if (dist[idx][s]+1 < dist[idx][u.F]) {
                dist[idx][u.F] = dist[idx][s]+1;
                // eist[idx][u.S] = dist[idx][u.F];
                q.push(u.F);
            }
        }
    }
}

int find_edge() {
    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,m) w[i] = 1;
        int val = ask(w);
        if (val == ans) r = mid-1;
        else l = mid;
    }
    return l;
}

int find_edge1() {
    // 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) {
    FOR(i,0,m) intree[i] = 1;
    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,v[s]) {
            if (d[s]+1 < d[u.F]) {
                d[u.F] = d[s]+1;
                if (e[u.S].y != u.F) swap(e[u.S].x, e[u.S].y);
                if (dist[idx][u.F] < dist[idx^1][u.F]) tour.PB({d[u.F],u.S});
                q.push(u.F);
            }
            else if (d[s]+1 == d[u.F]) intree[u.S] = 0;
        }
    }
    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);
    // cout << ans << ln;
    int edge = find_edge();
    // cout << "x y: " << e[edge].x << " " << e[edge].y << ln;
    int xs = e[edge].x, ys = e[edge].y;
    pre_bfs(xs,0);
    pre_bfs(ys,1);
    // cout << "xs ys: " << xs << " " << ys << ln;
    
    // FOR(i,0,n) {
    //     cout << i << ": ";
    //     FORX(u,v2[i]) cout << u.F << " ";
    //     cout << ln;
    // }
    // return;
    bfs(xs,0);
    int edge1 = find_edge1();
    int s = edge1 == -1 ? xs : e[edge1].y;
    // cout << xs << ln;
    // if (s == xs) while (true) int bruh = 0;
    bfs(ys,1);
    int edge2 = find_edge1();
    int t = edge2 == -1 ? ys : 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 2 ms 3368 KB Output is correct
2 Correct 2 ms 3280 KB Output is correct
3 Correct 2 ms 3280 KB Output is correct
4 Correct 2 ms 3372 KB Output is correct
5 Correct 2 ms 3280 KB Output is correct
6 Correct 2 ms 3280 KB Output is correct
7 Correct 2 ms 3280 KB Output is correct
8 Correct 2 ms 3280 KB Output is correct
9 Correct 2 ms 3408 KB Output is correct
10 Correct 2 ms 3280 KB Output is correct
11 Correct 2 ms 3280 KB Output is correct
12 Correct 2 ms 3280 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3536 KB Output is correct
2 Correct 11 ms 5076 KB Output is correct
3 Correct 146 ms 19280 KB Output is correct
4 Correct 119 ms 19080 KB Output is correct
5 Correct 101 ms 19172 KB Output is correct
6 Correct 119 ms 19132 KB Output is correct
7 Correct 124 ms 19220 KB Output is correct
8 Correct 123 ms 19148 KB Output is correct
9 Correct 119 ms 18920 KB Output is correct
10 Correct 127 ms 19220 KB Output is correct
11 Correct 105 ms 17844 KB Output is correct
12 Correct 128 ms 19008 KB Output is correct
13 Correct 103 ms 19200 KB Output is correct
14 Correct 127 ms 19152 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5004 KB Output is correct
2 Correct 18 ms 6432 KB Output is correct
3 Correct 39 ms 8248 KB Output is correct
4 Correct 117 ms 17248 KB Output is correct
5 Correct 70 ms 17268 KB Output is correct
6 Correct 67 ms 18492 KB Output is correct
7 Correct 83 ms 18744 KB Output is correct
8 Correct 81 ms 17304 KB Output is correct
9 Correct 88 ms 18376 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3536 KB Output is correct
2 Correct 15 ms 5136 KB Output is correct
3 Correct 92 ms 16212 KB Output is correct
4 Correct 103 ms 19160 KB Output is correct
5 Correct 96 ms 19172 KB Output is correct
6 Correct 125 ms 19112 KB Output is correct
7 Correct 135 ms 19188 KB Output is correct
8 Correct 127 ms 19164 KB Output is correct
9 Correct 120 ms 17716 KB Output is correct
10 Correct 141 ms 19236 KB Output is correct
11 Correct 127 ms 19156 KB Output is correct
12 Correct 149 ms 18924 KB Output is correct
13 Correct 131 ms 17888 KB Output is correct
14 Correct 134 ms 17852 KB Output is correct
15 Correct 125 ms 19188 KB Output is correct
16 Correct 126 ms 19296 KB Output is correct
17 Correct 132 ms 19168 KB Output is correct
18 Correct 104 ms 19120 KB Output is correct
19 Correct 124 ms 19128 KB Output is correct
20 Correct 134 ms 19192 KB Output is correct
21 Correct 104 ms 18780 KB Output is correct
22 Correct 96 ms 18784 KB Output is correct
23 Correct 96 ms 17108 KB Output is correct
24 Correct 88 ms 17364 KB Output is correct
25 Correct 129 ms 19164 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5036 KB Output is correct
2 Correct 15 ms 5216 KB Output is correct
3 Correct 134 ms 18504 KB Output is correct
4 Correct 124 ms 21040 KB Output is correct
5 Correct 159 ms 21472 KB Output is correct
6 Correct 188 ms 22992 KB Output is correct
7 Correct 148 ms 21424 KB Output is correct
8 Correct 211 ms 21328 KB Output is correct
9 Incorrect 118 ms 16528 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5004 KB Output is correct
2 Correct 12 ms 5260 KB Output is correct
3 Correct 122 ms 20188 KB Output is correct
4 Correct 181 ms 19140 KB Output is correct
5 Correct 168 ms 20836 KB Output is correct
6 Correct 147 ms 22688 KB Output is correct
7 Correct 169 ms 18796 KB Output is correct
8 Correct 134 ms 18852 KB Output is correct
9 Correct 144 ms 21088 KB Output is correct
10 Correct 163 ms 21608 KB Output is correct
11 Incorrect 147 ms 21288 KB Output is incorrect: {s, t} is wrong.
12 Halted 0 ms 0 KB -