oj.uz

Submission #783655

# Submission time Handle Problem Language Result Execution time Memory
783655 2023-07-15T07:36:29 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 205 ms 27780 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) {
    // tour.clear();
    // dfs(s,pa,vec);
    // FORX(u,tour) cout << u << " ";
    // cout << ln;
    int l = -1, r = m-1;
    // FOR(i,0,m) cout << intree[i] << " ";
    // cout << ln;
    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;
    }
    // cout << "s l: " << s << " " << tour[l] << ln;
    return l == -1 ? -1 : 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});
    d[start] = 0;
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        // cout << s << " ";
        FORX(u,vec[s]) {
            if (d[s]+1 < d[u.F]) {
                d[u.F] = d[s]+1;
                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);
    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;
    answer(s,t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9600 KB Output is correct
2 Correct 18 ms 11004 KB Output is correct
3 Correct 113 ms 23892 KB Output is correct
4 Correct 118 ms 23892 KB Output is correct
5 Correct 117 ms 23904 KB Output is correct
6 Correct 109 ms 23904 KB Output is correct
7 Correct 120 ms 23852 KB Output is correct
8 Correct 103 ms 23888 KB Output is correct
9 Correct 138 ms 24016 KB Output is correct
10 Correct 122 ms 23892 KB Output is correct
11 Correct 100 ms 23940 KB Output is correct
12 Correct 133 ms 23876 KB Output is correct
13 Correct 100 ms 23968 KB Output is correct
14 Correct 137 ms 23876 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11008 KB Output is correct
2 Correct 32 ms 12608 KB Output is correct
3 Correct 36 ms 13832 KB Output is correct
4 Correct 105 ms 23464 KB Output is correct
5 Correct 108 ms 23392 KB Output is correct
6 Correct 118 ms 23392 KB Output is correct
7 Correct 108 ms 23368 KB Output is correct
8 Correct 107 ms 23448 KB Output is correct
9 Correct 114 ms 23424 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9552 KB Output is correct
2 Correct 17 ms 11092 KB Output is correct
3 Correct 79 ms 21220 KB Output is correct
4 Correct 128 ms 24004 KB Output is correct
5 Correct 135 ms 23956 KB Output is correct
6 Correct 165 ms 23896 KB Output is correct
7 Correct 104 ms 23892 KB Output is correct
8 Correct 133 ms 23884 KB Output is correct
9 Correct 141 ms 23900 KB Output is correct
10 Correct 151 ms 23960 KB Output is correct
11 Correct 133 ms 23876 KB Output is correct
12 Correct 119 ms 23944 KB Output is correct
13 Correct 104 ms 23944 KB Output is correct
14 Correct 100 ms 23932 KB Output is correct
15 Correct 104 ms 23896 KB Output is correct
16 Correct 139 ms 23896 KB Output is correct
17 Correct 109 ms 23904 KB Output is correct
18 Correct 115 ms 23940 KB Output is correct
19 Correct 110 ms 23784 KB Output is correct
20 Correct 102 ms 23880 KB Output is correct
21 Correct 85 ms 23480 KB Output is correct
22 Correct 105 ms 23468 KB Output is correct
23 Correct 142 ms 23508 KB Output is correct
24 Correct 106 ms 23500 KB Output is correct
25 Correct 131 ms 23912 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11140 KB Output is correct
2 Correct 17 ms 11312 KB Output is correct
3 Correct 123 ms 24844 KB Output is correct
4 Correct 128 ms 25840 KB Output is correct
5 Correct 205 ms 27780 KB Output is correct
6 Incorrect 179 ms 27776 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 20 ms 11148 KB Output is correct
2 Correct 17 ms 11292 KB Output is correct
3 Partially correct 145 ms 25164 KB Output is partially correct
4 Partially correct 139 ms 25352 KB Output is partially correct
5 Incorrect 140 ms 25848 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -