oj.uz

Submission #421642

# Submission time Handle Problem Language Result Execution time Memory
421642 2021-06-09T10:21:10 Z xt0r3 Highway Tolls (IOI18_highway) C++14
51 / 100
 258 ms 262148 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;

constexpr int N = 1e5 + 5;
vector<int> w, lst;
vector<pair<int, int> > edges[N];

int n, m, a, b, d[N], s, t;
long long alap;

void dfs(int id, int de = 0, int par = -1){
    d[id] = de;
    for(pair<int, int> p : edges[id]){
        if(p.first != par){
            dfs(p.first, de + 1, id);
            lst.push_back(p.second);
        }
    }
}

int src(int l, int r){
    if(l == r) return (l == lst.size() ? -1 : lst[l]);
    int m = (l + r) / 2;

    for(int i = max(0, l); i <= m; i++) w[lst[i]] = 1;
    long long cur = ask(w);
    for(int i = max(0, l); i <= m; i++) w[lst[i]] = 0;

    return (cur > alap ? src(l, m) : src(m + 1, r));

}

void find_pair(int _N, std::vector<int> u, std::vector<int> v, int A, int B) {
    n = _N;
    m = u.size();
    a = A;
    b = B;
    w.assign(m, 0);
    alap = ask(w);
    for(int i = 0; i < m; i++){
        edges[u[i]].emplace_back(v[i], i);
        edges[v[i]].emplace_back(u[i], i);
    }
    dfs(0);
    sort(lst.begin(), lst.end(), [&u, &v](int x, int y){return max(d[u[x]], d[v[x]]) > max(d[u[y]], d[v[y]]);});
    int id = src(0, lst.size() - 1);
    pair<int, int> p1 = make_pair(u[id], v[id]), p2;

    lst.clear();
    dfs(p1.first, 0, p1.second);
    if(lst.empty()){
        s = p1.first;
    }
    else{
        sort(lst.begin(), lst.end(), [&u, &v](int x, int y){return max(d[u[x]], d[v[x]]) > max(d[u[y]], d[v[y]]);});
        id = src(0, lst.size());
        if(id == -1) s = p1.first;
        else s = (d[u[id]] > d[v[id]] ? u[id] : v[id]);
    }

    swap(p1.first, p1.second);//ugyanez forditva
    lst.clear();
    dfs(p1.first, 0, p1.second);
    if(lst.empty()){
        t = p1.first;
    }
    else{
        sort(lst.begin(), lst.end(), [&u, &v](int x, int y){return max(d[u[x]], d[v[x]]) > max(d[u[y]], d[v[y]]);});
        id = src(0, lst.size());
        if(id == -1) t = p1.first;
        else t = (d[u[id]] > d[v[id]] ? u[id] : v[id]);
    }
    lst.clear();

  answer(s, t);
}

Compilation message

highway.cpp: In function 'int src(int, int)':
highway.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if(l == r) return (l == lst.size() ? -1 : lst[l]);
      |                        ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2632 KB Output is correct
2 Correct 3 ms 2760 KB Output is correct
3 Correct 2 ms 2632 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2632 KB Output is correct
6 Correct 2 ms 2632 KB Output is correct
7 Correct 2 ms 2760 KB Output is correct
8 Correct 2 ms 2632 KB Output is correct
9 Correct 2 ms 2632 KB Output is correct
10 Correct 2 ms 2632 KB Output is correct
11 Correct 2 ms 2632 KB Output is correct
12 Correct 3 ms 2632 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2664 KB Output is correct
2 Correct 16 ms 3356 KB Output is correct
3 Correct 187 ms 8644 KB Output is correct
4 Correct 189 ms 8720 KB Output is correct
5 Correct 186 ms 8656 KB Output is correct
6 Correct 141 ms 8760 KB Output is correct
7 Correct 193 ms 8764 KB Output is correct
8 Correct 177 ms 8768 KB Output is correct
9 Correct 161 ms 8768 KB Output is correct
10 Correct 158 ms 8644 KB Output is correct
11 Correct 167 ms 9544 KB Output is correct
12 Correct 223 ms 10212 KB Output is correct
13 Correct 258 ms 9684 KB Output is correct
14 Correct 233 ms 9656 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3912 KB Output is correct
2 Correct 36 ms 5100 KB Output is correct
3 Correct 52 ms 6324 KB Output is correct
4 Correct 123 ms 13800 KB Output is correct
5 Correct 222 ms 13828 KB Output is correct
6 Correct 147 ms 13828 KB Output is correct
7 Correct 146 ms 13880 KB Output is correct
8 Correct 125 ms 13892 KB Output is correct
9 Correct 163 ms 13752 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2632 KB Output is correct
2 Correct 20 ms 3360 KB Output is correct
3 Correct 169 ms 7484 KB Output is correct
4 Correct 195 ms 8788 KB Output is correct
5 Correct 178 ms 8724 KB Output is correct
6 Correct 187 ms 8764 KB Output is correct
7 Correct 179 ms 8716 KB Output is correct
8 Correct 193 ms 8640 KB Output is correct
9 Correct 172 ms 8660 KB Output is correct
10 Correct 151 ms 8756 KB Output is correct
11 Correct 189 ms 9256 KB Output is correct
12 Correct 229 ms 10208 KB Output is correct
13 Correct 206 ms 9840 KB Output is correct
14 Correct 176 ms 10168 KB Output is correct
15 Correct 177 ms 8780 KB Output is correct
16 Correct 166 ms 8716 KB Output is correct
17 Correct 169 ms 9924 KB Output is correct
18 Correct 208 ms 9896 KB Output is correct
19 Correct 196 ms 8716 KB Output is correct
20 Correct 254 ms 10560 KB Output is correct
21 Correct 167 ms 9152 KB Output is correct
22 Correct 114 ms 9148 KB Output is correct
23 Correct 167 ms 9004 KB Output is correct
24 Correct 138 ms 9528 KB Output is correct
25 Correct 163 ms 13152 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 246 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 246 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -