oj.uz

Submission #783666

# Submission time Handle Problem Language Result Execution time Memory
783666 2023-07-15T08:01:44 Z Magikarp4000 Highway Tolls (IOI18_highway) C++17
51 / 100
 203 ms 27840 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] = 0LL;
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        // cout << s << " ";
        FORX(u,vec[s]) {
            if (d[u.F] == INF) {
                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:157:38: warning: unused variable 'abc' [-Wunused-variable]
  157 |     if (ans1 > ans) while (true) int abc = 0;
      |                                      ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9472 KB Output is correct
2 Correct 6 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 6 ms 9400 KB Output is correct
6 Correct 4 ms 9424 KB Output is correct
7 Correct 4 ms 9424 KB Output is correct
8 Correct 6 ms 9424 KB Output is correct
9 Correct 4 ms 9368 KB Output is correct
10 Correct 4 ms 9472 KB Output is correct
11 Correct 5 ms 9424 KB Output is correct
12 Correct 5 ms 9424 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 16 ms 11020 KB Output is correct
3 Correct 107 ms 23884 KB Output is correct
4 Correct 126 ms 23888 KB Output is correct
5 Correct 107 ms 23892 KB Output is correct
6 Correct 128 ms 23892 KB Output is correct
7 Correct 134 ms 23892 KB Output is correct
8 Correct 131 ms 23900 KB Output is correct
9 Correct 102 ms 23896 KB Output is correct
10 Correct 136 ms 23892 KB Output is correct
11 Correct 138 ms 23964 KB Output is correct
12 Correct 112 ms 23968 KB Output is correct
13 Correct 105 ms 24008 KB Output is correct
14 Correct 127 ms 23980 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 12552 KB Output is correct
3 Correct 34 ms 13952 KB Output is correct
4 Correct 99 ms 23452 KB Output is correct
5 Correct 85 ms 23444 KB Output is correct
6 Correct 97 ms 23492 KB Output is correct
7 Correct 93 ms 23460 KB Output is correct
8 Correct 76 ms 23424 KB Output is correct
9 Correct 118 ms 23460 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9564 KB Output is correct
2 Correct 14 ms 11004 KB Output is correct
3 Correct 78 ms 21212 KB Output is correct
4 Correct 129 ms 23884 KB Output is correct
5 Correct 103 ms 23900 KB Output is correct
6 Correct 103 ms 23896 KB Output is correct
7 Correct 130 ms 23892 KB Output is correct
8 Correct 104 ms 23880 KB Output is correct
9 Correct 155 ms 23908 KB Output is correct
10 Correct 103 ms 24008 KB Output is correct
11 Correct 116 ms 23916 KB Output is correct
12 Correct 103 ms 23964 KB Output is correct
13 Correct 106 ms 24000 KB Output is correct
14 Correct 133 ms 23876 KB Output is correct
15 Correct 142 ms 23904 KB Output is correct
16 Correct 113 ms 23904 KB Output is correct
17 Correct 124 ms 23948 KB Output is correct
18 Correct 131 ms 23896 KB Output is correct
19 Correct 122 ms 23792 KB Output is correct
20 Correct 146 ms 23960 KB Output is correct
21 Correct 103 ms 23464 KB Output is correct
22 Correct 81 ms 23428 KB Output is correct
23 Correct 112 ms 23480 KB Output is correct
24 Correct 96 ms 23392 KB Output is correct
25 Correct 136 ms 23940 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11240 KB Output is correct
2 Correct 16 ms 11276 KB Output is correct
3 Correct 149 ms 24868 KB Output is correct
4 Correct 149 ms 25852 KB Output is correct
5 Correct 203 ms 27780 KB Output is correct
6 Incorrect 160 ms 27840 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 11208 KB Output is correct
2 Correct 18 ms 11188 KB Output is correct
3 Partially correct 115 ms 24948 KB Output is partially correct
4 Partially correct 148 ms 25472 KB Output is partially correct
5 Incorrect 134 ms 25832 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -