oj.uz

Submission #783672

# Submission time Handle Problem Language Result Execution time Memory
783672 2023-07-15T08:09:08 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 219 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;
    if (edge == -1) while (true) int abc = 1;
    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;
    // 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:135:38: warning: unused variable 'abc' [-Wunused-variable]
  135 |     if (edge == -1) while (true) int abc = 1;
      |                                      ^~~

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 9484 KB Output is correct
3 Correct 4 ms 9424 KB Output is correct
4 Correct 5 ms 9436 KB Output is correct
5 Correct 5 ms 9476 KB Output is correct
6 Correct 4 ms 9424 KB Output is correct
7 Correct 5 ms 9424 KB Output is correct
8 Correct 4 ms 9424 KB Output is correct
9 Correct 4 ms 9372 KB Output is correct
10 Correct 5 ms 9424 KB Output is correct
11 Correct 4 ms 9424 KB Output is correct
12 Correct 6 ms 9368 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9552 KB Output is correct
2 Correct 15 ms 11000 KB Output is correct
3 Correct 138 ms 23888 KB Output is correct
4 Correct 134 ms 23896 KB Output is correct
5 Correct 110 ms 23896 KB Output is correct
6 Correct 117 ms 23900 KB Output is correct
7 Correct 109 ms 23892 KB Output is correct
8 Correct 108 ms 23908 KB Output is correct
9 Correct 118 ms 23908 KB Output is correct
10 Correct 129 ms 23972 KB Output is correct
11 Correct 103 ms 23932 KB Output is correct
12 Correct 132 ms 23960 KB Output is correct
13 Correct 125 ms 23912 KB Output is correct
14 Correct 110 ms 23876 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11020 KB Output is correct
2 Correct 21 ms 12556 KB Output is correct
3 Correct 28 ms 13960 KB Output is correct
4 Correct 102 ms 23496 KB Output is correct
5 Correct 124 ms 23524 KB Output is correct
6 Correct 78 ms 23372 KB Output is correct
7 Correct 109 ms 23480 KB Output is correct
8 Correct 78 ms 23488 KB Output is correct
9 Correct 75 ms 23492 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9560 KB Output is correct
2 Correct 16 ms 11092 KB Output is correct
3 Correct 74 ms 21208 KB Output is correct
4 Correct 132 ms 23840 KB Output is correct
5 Correct 139 ms 23884 KB Output is correct
6 Correct 119 ms 24012 KB Output is correct
7 Correct 133 ms 23884 KB Output is correct
8 Correct 125 ms 23872 KB Output is correct
9 Correct 132 ms 23904 KB Output is correct
10 Correct 126 ms 23900 KB Output is correct
11 Correct 142 ms 23900 KB Output is correct
12 Correct 127 ms 23956 KB Output is correct
13 Correct 120 ms 23908 KB Output is correct
14 Correct 115 ms 23900 KB Output is correct
15 Correct 134 ms 23896 KB Output is correct
16 Correct 139 ms 23892 KB Output is correct
17 Correct 113 ms 23924 KB Output is correct
18 Correct 142 ms 23932 KB Output is correct
19 Correct 129 ms 24012 KB Output is correct
20 Correct 109 ms 23868 KB Output is correct
21 Correct 92 ms 23464 KB Output is correct
22 Correct 114 ms 23472 KB Output is correct
23 Correct 109 ms 23500 KB Output is correct
24 Correct 112 ms 23460 KB Output is correct
25 Correct 117 ms 23952 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 11200 KB Output is correct
2 Correct 19 ms 11268 KB Output is correct
3 Correct 139 ms 24856 KB Output is correct
4 Correct 153 ms 25836 KB Output is correct
5 Correct 189 ms 27784 KB Output is correct
6 Incorrect 219 ms 27780 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 17 ms 11216 KB Output is correct
2 Correct 19 ms 11288 KB Output is correct
3 Partially correct 146 ms 24952 KB Output is partially correct
4 Partially correct 164 ms 25340 KB Output is partially correct
5 Incorrect 151 ms 25948 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -