oj.uz

Submission #783671

# Submission time Handle Problem Language Result Execution time Memory
783671 2023-07-15T08:08:02 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) {
    // tour.clear();
    // dfs(s,pa,vec);
    // FORX(u,tour) cout << u << " ";
    // cout << ln;
    int l = 0, 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});
    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;
    // cout << "S T: " << s << " " << t << ln;
    FOR(i,0,m) w[i] = 0;
    int ans1 = ask(w);
    if (ans1 < ans) while (true) int abc = 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:160:38: warning: unused variable 'abc' [-Wunused-variable]
  160 |     if (ans1 < ans) while (true) int abc = 0;
      |                                      ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9476 KB Output is correct
2 Correct 5 ms 9424 KB Output is correct
3 Correct 5 ms 9480 KB Output is correct
4 Correct 5 ms 9424 KB Output is correct
5 Correct 4 ms 9424 KB Output is correct
6 Correct 4 ms 9424 KB Output is correct
7 Correct 4 ms 9424 KB Output is correct
8 Correct 5 ms 9476 KB Output is correct
9 Correct 6 ms 9404 KB Output is correct
10 Correct 6 ms 9424 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 5 ms 9552 KB Output is correct
2 Correct 17 ms 11016 KB Output is correct
3 Correct 134 ms 23872 KB Output is correct
4 Correct 118 ms 23892 KB Output is correct
5 Correct 111 ms 23880 KB Output is correct
6 Correct 153 ms 23892 KB Output is correct
7 Correct 116 ms 23896 KB Output is correct
8 Correct 108 ms 23888 KB Output is correct
9 Correct 135 ms 23912 KB Output is correct
10 Correct 112 ms 23876 KB Output is correct
11 Correct 153 ms 24004 KB Output is correct
12 Correct 118 ms 23940 KB Output is correct
13 Correct 138 ms 24000 KB Output is correct
14 Correct 105 ms 23884 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11020 KB Output is correct
2 Correct 26 ms 12620 KB Output is correct
3 Correct 27 ms 13836 KB Output is correct
4 Correct 73 ms 23500 KB Output is correct
5 Correct 95 ms 23460 KB Output is correct
6 Correct 117 ms 23492 KB Output is correct
7 Correct 111 ms 23428 KB Output is correct
8 Correct 95 ms 23400 KB Output is correct
9 Correct 102 ms 23460 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9588 KB Output is correct
2 Correct 13 ms 11020 KB Output is correct
3 Correct 84 ms 21208 KB Output is correct
4 Correct 105 ms 23892 KB Output is correct
5 Correct 131 ms 23896 KB Output is correct
6 Correct 127 ms 23900 KB Output is correct
7 Correct 130 ms 23888 KB Output is correct
8 Correct 118 ms 23876 KB Output is correct
9 Correct 131 ms 23896 KB Output is correct
10 Correct 125 ms 23912 KB Output is correct
11 Correct 113 ms 23872 KB Output is correct
12 Correct 118 ms 23960 KB Output is correct
13 Correct 147 ms 23988 KB Output is correct
14 Correct 123 ms 23944 KB Output is correct
15 Correct 116 ms 23892 KB Output is correct
16 Correct 142 ms 23964 KB Output is correct
17 Correct 108 ms 24000 KB Output is correct
18 Correct 144 ms 23904 KB Output is correct
19 Correct 112 ms 23872 KB Output is correct
20 Correct 112 ms 23944 KB Output is correct
21 Correct 97 ms 23412 KB Output is correct
22 Correct 78 ms 23408 KB Output is correct
23 Correct 114 ms 23512 KB Output is correct
24 Correct 89 ms 23484 KB Output is correct
25 Correct 110 ms 23932 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 11148 KB Output is correct
2 Correct 18 ms 11316 KB Output is correct
3 Correct 168 ms 24856 KB Output is correct
4 Correct 145 ms 25932 KB Output is correct
5 Correct 147 ms 27772 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 15 ms 11200 KB Output is correct
2 Correct 16 ms 11292 KB Output is correct
3 Partially correct 158 ms 24948 KB Output is partially correct
4 Partially correct 148 ms 25348 KB Output is partially correct
5 Incorrect 163 ms 25840 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -