oj.uz

Submission #116153

# Submission time Handle Problem Language Result Execution time Memory
116153 2019-06-11T03:21:19 Z RezwanArefin01 Highway Tolls (IOI18_highway) C++17
7 / 100
 288 ms 9784 KB 
#include <bits/stdc++.h>
using namespace std;
#include "highway.h"

typedef long long ll; 

const int MX = 9e4 + 5; 
vector<int> adj[MX], q, t;
int l[MX], r[MX], a, b, n, m, comp[MX];

int findEdge() {
    int lo = 0, hi = m - 1, e;
    ll base = ask(q);

    while(lo <= hi) {
        int mid = lo + hi >> 1; 
        for(int i = 0; i < m; ++i) 
            q[i] = i <= mid;
        if(ask(q) != base) 
            e = mid, hi = mid - 1;
        else lo = mid + 1; 
    }

    return e;
}

void bfs(int root, vector<int> &d, int c, bool store = 0) {
    queue<int> Q; 
    d[root] = 0; 
    Q.push(root); 

    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int i : adj[u]) {
            int v = u ^ l[i] ^ r[i]; 
            if(comp[v] == c && d[v] == -1) {
                d[v] = d[u] + 1; 
                Q.push(v);
                if(store) t.push_back(i);
            }
        }
    }
}

int find(int c, vector<int> &d) {
    sort(t.begin(), t.end(), [&](int i, int j) {
        return max(d[l[i]], d[r[i]]) < max(d[l[j]], d[r[j]]); 
    });

    q = vector<int> (m, 0);
    for(int i : t) q[i] = 1; 

    ll base = ask(q); 

    int lo = 0, hi = (int) t.size() - 1, e;
    while(lo <= hi) {
        int mid = lo + hi >> 1; 
        q = vector<int> (m, 0); 
        for(int i = 0; i <= mid; ++i) 
            q[t[i]] = 1; 
        if(ask(q) == base) 
            e = t[mid], hi = mid - 1; 
        else lo = mid + 1; 
    }

    return d[l[e]] > d[r[e]] ? l[e] : r[e];
}

void find_pair(int _n, vector<int> U, vector<int> V, int _a, int _b) {
    n = _n, a = _a, b = _b;
    m = U.size(); 
    copy(U.begin(), U.end(), l); 
    copy(V.begin(), V.end(), r); 

    for(int i = 0; i < m; ++i) {
        adj[l[i]].push_back(i);
        adj[r[i]].push_back(i);
    }

    q = vector<int> (m, 0);

    int e = findEdge(); 

    vector<int> du (n, -1), dv (n, -1); 
    bfs(l[e], du, 0); 
    bfs(r[e], dv, 0); 

    for(int i = 0; i < n; ++i) {
        comp[i] = du[i] > dv[i];
    }   

    du = vector<int> (n, -1); 
    bfs(l[e], du, 0, 1); 
    int S = t.size() ? find(0, du) : l[e]; 

    t.clear(); 

    dv = vector<int> (n, -1);
    bfs(r[e], dv, 1, 1);
    int T = t.size() ? find(0, dv) : r[e]; 

    answer(S, T);
}

Compilation message

highway.cpp: In function 'int findEdge()':
highway.cpp:16:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~
highway.cpp: In function 'int find(int, std::vector<int>&)':
highway.cpp:57:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~
highway.cpp: In function 'int findEdge()':
highway.cpp:24:12: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return e;
            ^
highway.cpp: In function 'int find(int, std::vector<int>&)':
highway.cpp:66:17: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return d[l[e]] > d[r[e]] ? l[e] : r[e];
              ~~~^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2444 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2588 KB Output is correct
2 Correct 27 ms 3276 KB Output is correct
3 Correct 234 ms 9636 KB Output is correct
4 Correct 211 ms 9760 KB Output is correct
5 Correct 240 ms 9768 KB Output is correct
6 Correct 207 ms 9696 KB Output is correct
7 Correct 224 ms 9780 KB Output is correct
8 Correct 223 ms 9784 KB Output is correct
9 Correct 221 ms 9716 KB Output is correct
10 Correct 253 ms 9772 KB Output is correct
11 Correct 253 ms 9628 KB Output is correct
12 Correct 258 ms 9492 KB Output is correct
13 Correct 288 ms 9652 KB Output is correct
14 Correct 193 ms 9552 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3232 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2604 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 3280 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 3204 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -