oj.uz

Submission #783817

# Submission time Handle Problem Language Result Execution time Memory
783817 2023-07-15T10:50:30 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
7 / 100
 226 ms 22872 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], 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 ? s : e[edge2].y;
    // cout << "S T: " << s << " " << t << ln;
    FOR(i,0,m) w[i] = 0;
    answer(s,t);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3280 KB Output is correct
2 Correct 2 ms 3380 KB Output is correct
3 Correct 2 ms 3280 KB Output is correct
4 Incorrect 2 ms 3408 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3536 KB Output is correct
2 Correct 13 ms 5064 KB Output is correct
3 Correct 162 ms 19180 KB Output is correct
4 Correct 102 ms 19100 KB Output is correct
5 Correct 138 ms 19100 KB Output is correct
6 Correct 105 ms 19164 KB Output is correct
7 Correct 112 ms 19216 KB Output is correct
8 Correct 108 ms 19180 KB Output is correct
9 Correct 108 ms 18920 KB Output is correct
10 Correct 135 ms 19180 KB Output is correct
11 Correct 125 ms 17824 KB Output is correct
12 Correct 106 ms 18916 KB Output is correct
13 Correct 149 ms 19184 KB Output is correct
14 Correct 126 ms 19180 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3536 KB Output is correct
2 Correct 12 ms 5164 KB Output is correct
3 Correct 109 ms 16312 KB Output is correct
4 Correct 111 ms 19152 KB Output is correct
5 Correct 118 ms 19168 KB Output is correct
6 Correct 124 ms 19192 KB Output is correct
7 Correct 91 ms 19196 KB Output is correct
8 Correct 97 ms 19068 KB Output is correct
9 Correct 138 ms 17720 KB Output is correct
10 Correct 130 ms 19108 KB Output is correct
11 Correct 141 ms 19156 KB Output is correct
12 Correct 138 ms 19028 KB Output is correct
13 Correct 134 ms 17928 KB Output is correct
14 Correct 130 ms 17868 KB Output is correct
15 Correct 119 ms 19172 KB Output is correct
16 Incorrect 118 ms 19204 KB Output is incorrect: {s, t} is wrong.
17 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5004 KB Output is correct
2 Correct 14 ms 5236 KB Output is correct
3 Correct 139 ms 18508 KB Output is correct
4 Correct 137 ms 21048 KB Output is correct
5 Correct 195 ms 21472 KB Output is correct
6 Correct 200 ms 22872 KB Output is correct
7 Correct 226 ms 21436 KB Output is correct
8 Correct 155 ms 21344 KB Output is correct
9 Incorrect 126 ms 16640 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 Incorrect 16 ms 4996 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -