oj.uz

Submission #783674

# Submission time Handle Problem Language Result Execution time Memory
783674 2023-07-15T08:11:37 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 207 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_tree(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_tree(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_tree(xs,edge,v,v1);
    int edge1 = find_edge1(xs,edge,v1);
    int32_t s = edge1 == -1 ? xs : e[edge1].y;
    bfs_tree(s,edge1,v,v1);
    int edge2 = find_edge1(s,edge1,v1);
    int32_t t = edge2 == -1 ? s : e[edge2].y;
    if (edge2 == -1) while (true) int bruh = 0;
    // 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:150:39: warning: unused variable 'bruh' [-Wunused-variable]
  150 |     if (edge2 == -1) 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 7 ms 9424 KB Output is correct
3 Correct 5 ms 9424 KB Output is correct
4 Correct 5 ms 9424 KB Output is correct
5 Correct 4 ms 9424 KB Output is correct
6 Correct 5 ms 9372 KB Output is correct
7 Correct 5 ms 9480 KB Output is correct
8 Correct 5 ms 9552 KB Output is correct
9 Correct 5 ms 9444 KB Output is correct
10 Correct 5 ms 9472 KB Output is correct
11 Correct 6 ms 9472 KB Output is correct
12 Correct 4 ms 9476 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9604 KB Output is correct
2 Correct 16 ms 11004 KB Output is correct
3 Correct 113 ms 23908 KB Output is correct
4 Correct 103 ms 23904 KB Output is correct
5 Correct 118 ms 23892 KB Output is correct
6 Correct 121 ms 23928 KB Output is correct
7 Correct 126 ms 23892 KB Output is correct
8 Correct 151 ms 23896 KB Output is correct
9 Correct 109 ms 23888 KB Output is correct
10 Correct 136 ms 23888 KB Output is correct
11 Correct 126 ms 23980 KB Output is correct
12 Correct 154 ms 23876 KB Output is correct
13 Correct 110 ms 23880 KB Output is correct
14 Correct 161 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 25 ms 12608 KB Output is correct
3 Correct 31 ms 13836 KB Output is correct
4 Correct 90 ms 23484 KB Output is correct
5 Correct 100 ms 23396 KB Output is correct
6 Correct 91 ms 23440 KB Output is correct
7 Correct 88 ms 23456 KB Output is correct
8 Correct 76 ms 23488 KB Output is correct
9 Correct 119 ms 23396 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 11100 KB Output is correct
3 Correct 91 ms 21320 KB Output is correct
4 Correct 136 ms 23892 KB Output is correct
5 Correct 111 ms 23888 KB Output is correct
6 Correct 126 ms 23904 KB Output is correct
7 Correct 129 ms 23892 KB Output is correct
8 Correct 110 ms 23880 KB Output is correct
9 Correct 109 ms 23896 KB Output is correct
10 Correct 121 ms 24016 KB Output is correct
11 Correct 133 ms 23936 KB Output is correct
12 Correct 162 ms 24000 KB Output is correct
13 Correct 101 ms 23996 KB Output is correct
14 Correct 137 ms 23964 KB Output is correct
15 Correct 133 ms 23896 KB Output is correct
16 Correct 121 ms 23900 KB Output is correct
17 Correct 134 ms 23968 KB Output is correct
18 Correct 133 ms 23884 KB Output is correct
19 Correct 118 ms 23796 KB Output is correct
20 Correct 112 ms 23940 KB Output is correct
21 Correct 80 ms 23416 KB Output is correct
22 Correct 98 ms 23416 KB Output is correct
23 Correct 109 ms 23480 KB Output is correct
24 Correct 128 ms 23492 KB Output is correct
25 Correct 119 ms 23932 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11148 KB Output is correct
2 Correct 20 ms 11300 KB Output is correct
3 Correct 137 ms 24856 KB Output is correct
4 Correct 162 ms 25836 KB Output is correct
5 Correct 166 ms 27780 KB Output is correct
6 Incorrect 207 ms 27784 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 18 ms 11276 KB Output is correct
2 Correct 16 ms 11276 KB Output is correct
3 Partially correct 142 ms 24956 KB Output is partially correct
4 Partially correct 187 ms 25360 KB Output is partially correct
5 Incorrect 161 ms 25852 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -