oj.uz

Submission #783705

# Submission time Handle Problem Language Result Execution time Memory
783705 2023-07-15T08:44:17 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 217 ms 27784 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], v2[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+1)/2;
        FOR(i,mid,r+1) w[i] = 1;
        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;
    int l = -1, r = tour.size()-1;
    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;
        int val = ask(w);
        if (val == ans) r = mid-1;
        else l = mid;
    }
    // cout << "s l: " << s << " " << tour[l] << 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]+1 < 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};
            }
        }
    }
    FORX(u,tour) intree[u.S] = 1;
    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);
    int edge = find_edge(0);
    // cout << edge << 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;
    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);
}

Compilation message

highway.cpp: In function 'void find_pair(int32_t, std::vector<int>, std::vector<int>, int32_t, int32_t)':
highway.cpp:147:35: warning: unused variable 'bruh' [-Wunused-variable]
  147 |     if (s == xs) while (true) int bruh = 0;
      |                                   ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9424 KB Output is correct
2 Correct 5 ms 9476 KB Output is correct
3 Correct 6 ms 9424 KB Output is correct
4 Correct 4 ms 9424 KB Output is correct
5 Correct 4 ms 9472 KB Output is correct
6 Correct 5 ms 9424 KB Output is correct
7 Correct 4 ms 9476 KB Output is correct
8 Correct 4 ms 9424 KB Output is correct
9 Correct 4 ms 9424 KB Output is correct
10 Correct 4 ms 9424 KB Output is correct
11 Correct 4 ms 9424 KB Output is correct
12 Correct 4 ms 9424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9552 KB Output is correct
2 Correct 13 ms 10996 KB Output is correct
3 Correct 145 ms 23896 KB Output is correct
4 Correct 154 ms 24004 KB Output is correct
5 Correct 128 ms 23888 KB Output is correct
6 Correct 121 ms 23888 KB Output is correct
7 Correct 128 ms 23892 KB Output is correct
8 Correct 135 ms 23892 KB Output is correct
9 Correct 119 ms 23940 KB Output is correct
10 Correct 145 ms 23904 KB Output is correct
11 Correct 122 ms 24000 KB Output is correct
12 Correct 106 ms 23988 KB Output is correct
13 Correct 135 ms 23976 KB Output is correct
14 Correct 148 ms 23968 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11020 KB Output is correct
2 Correct 24 ms 12552 KB Output is correct
3 Correct 27 ms 13844 KB Output is correct
4 Correct 78 ms 23460 KB Output is correct
5 Correct 94 ms 23420 KB Output is correct
6 Correct 74 ms 23436 KB Output is correct
7 Correct 99 ms 23468 KB Output is correct
8 Correct 125 ms 23492 KB Output is correct
9 Correct 113 ms 23376 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9552 KB Output is correct
2 Correct 16 ms 10996 KB Output is correct
3 Correct 116 ms 21212 KB Output is correct
4 Correct 105 ms 23880 KB Output is correct
5 Correct 100 ms 23900 KB Output is correct
6 Correct 122 ms 23904 KB Output is correct
7 Correct 137 ms 23896 KB Output is correct
8 Correct 105 ms 23936 KB Output is correct
9 Correct 155 ms 23904 KB Output is correct
10 Correct 104 ms 23900 KB Output is correct
11 Correct 122 ms 23896 KB Output is correct
12 Correct 131 ms 23972 KB Output is correct
13 Correct 104 ms 23916 KB Output is correct
14 Correct 129 ms 23940 KB Output is correct
15 Correct 134 ms 23888 KB Output is correct
16 Correct 103 ms 23900 KB Output is correct
17 Correct 133 ms 23952 KB Output is correct
18 Correct 145 ms 23892 KB Output is correct
19 Correct 144 ms 24040 KB Output is correct
20 Correct 153 ms 23888 KB Output is correct
21 Correct 113 ms 23448 KB Output is correct
22 Correct 108 ms 23416 KB Output is correct
23 Correct 88 ms 23500 KB Output is correct
24 Correct 89 ms 23476 KB Output is correct
25 Correct 101 ms 23900 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11200 KB Output is correct
2 Correct 21 ms 11264 KB Output is correct
3 Correct 170 ms 24868 KB Output is correct
4 Correct 131 ms 25948 KB Output is correct
5 Correct 217 ms 27784 KB Output is correct
6 Incorrect 160 ms 27768 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11148 KB Output is correct
2 Correct 16 ms 11308 KB Output is correct
3 Partially correct 130 ms 24960 KB Output is partially correct
4 Partially correct 156 ms 25356 KB Output is partially correct
5 Incorrect 164 ms 25840 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -