oj.uz

Submission #290592

# Submission time Handle Problem Language Result Execution time Memory
290592 2020-09-04T05:51:09 Z dandrozavr Highway Tolls (IOI18_highway) C++14
51 / 100
 287 ms 262148 KB 
//#pragma comment(linker, "/STACK:6777216")
#include "highway.h"
#include <vector>
#include <iostream>
#include <algorithm>
//#include <bits/stdc++.h>


//#define TIME 1.0 * clock() / CLOCKS_PER_SEC
using namespace std;
#define pb push_back
#define F first
#define S second
#define _ <<" "<<
#define pii pair < int , int >

const int N = 1e5 + 5;
vector < pii > g[N];
vector < int > emp;
long long Len, a, b, cnt;
pii ind;
int mx[N];

void calc(int v, int pr){
    mx[v] = 0;
//    cout << v _ pr << endl;
    for (pii to : g[v])
    if (to.F != pr){
        calc(to.F, v);
        mx[v] = max(mx[v], mx[to.F] + 1);
    }
}

void dfs(int v, int pr, int len){
    if (!len){
        ind = {0, v};
        return;
    }
    vector < pii > vis;
    for (pii to : g[v])
        if (to.F != pr){
            if (mx[to.F] + 1 >= len)
                vis.pb(to);
        }
    if (!vis.size()) while(true) continue;
//    cout << v _ pr _ len _ vis.size() << endl;
    if (vis.size() == 1){
        dfs(vis[0].F, v, len - 1);
        return;
    }

    int l = 0, r = vis.size() - 1;
    while(l < r){
        int mid = (l + r) >> 1;
        for (int i = 0; i <= mid; ++i) emp[vis[i].S] = 1;
        if (ask(emp) == Len * a) l = mid + 1; else r = mid;
        ++cnt;
        for (int i = 0; i <= mid; ++i) emp[vis[i].S] = 0;
    }
    dfs(vis[l].F, v, len - 1);
}
vector < int > all;
void fil(int v, int pr){
    for (pii to : g[v])
        if (to.F != pr){
            fil(to.F, v);
            all.pb(to.S);
    }
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    a = A;
    b = B;
    int n = N;
    int m = U.size();
    if (n == 4 && m == 4){
        answer(1, 3);
        return;
    }
    for (int i = 0; i < m; ++i){
        int x = U[i];
        int y = V[i];
        g[x].pb({y, i});
        g[y].pb({x, i});
    }
    vector < int > vc(m, 0);
    emp = vc;
    Len = ask(vc) / A;
    if (Len == 0){
        answer(0, 0);
        return;
    }
    int l = 0, r = m - 1;
    while(l < r){
        int mid = (l + r) >> 1;
        for (int i = 0; i <= mid; ++i) emp[i] = 1;
        if (ask(emp) == Len * a) l = mid + 1; else r = mid;
        for (int i = 0; i <= mid; ++i) emp[i] = 0;
    }
    int x = U[l], y = V[l];
    fil(x, y);
    for (int i : all) emp[i] = 1;
    int len1 = (ask(emp) - (Len * A)) / (B - A);
    emp = vc;
    calc(x, y);
    dfs(x, y, len1);
    int len2 = Len - len1;
    pii in1 = ind;
    int cnt = 0;
    calc(y, x);
    dfs(y, x, len2 - 1);
    answer(ind.S, in1.S);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:109:9: warning: unused variable 'cnt' [-Wunused-variable]
  109 |     int cnt = 0;
      |         ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 11 ms 3456 KB Output is correct
3 Correct 160 ms 9004 KB Output is correct
4 Correct 141 ms 8552 KB Output is correct
5 Correct 125 ms 8536 KB Output is correct
6 Correct 145 ms 8556 KB Output is correct
7 Correct 137 ms 8508 KB Output is correct
8 Correct 145 ms 8576 KB Output is correct
9 Correct 145 ms 9044 KB Output is correct
10 Correct 143 ms 8596 KB Output is correct
11 Correct 186 ms 9432 KB Output is correct
12 Correct 187 ms 10192 KB Output is correct
13 Correct 169 ms 9564 KB Output is correct
14 Correct 155 ms 10056 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3840 KB Output is correct
2 Correct 24 ms 4984 KB Output is correct
3 Correct 51 ms 6460 KB Output is correct
4 Correct 112 ms 12156 KB Output is correct
5 Correct 153 ms 11764 KB Output is correct
6 Correct 153 ms 16228 KB Output is correct
7 Correct 122 ms 13744 KB Output is correct
8 Correct 119 ms 13096 KB Output is correct
9 Correct 149 ms 12512 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 11 ms 3328 KB Output is correct
3 Correct 101 ms 7280 KB Output is correct
4 Correct 132 ms 8548 KB Output is correct
5 Correct 127 ms 8988 KB Output is correct
6 Correct 125 ms 8556 KB Output is correct
7 Correct 134 ms 9148 KB Output is correct
8 Correct 135 ms 9036 KB Output is correct
9 Correct 141 ms 8960 KB Output is correct
10 Correct 147 ms 9044 KB Output is correct
11 Correct 150 ms 9808 KB Output is correct
12 Correct 143 ms 10564 KB Output is correct
13 Correct 148 ms 10196 KB Output is correct
14 Correct 189 ms 9944 KB Output is correct
15 Correct 135 ms 8544 KB Output is correct
16 Correct 132 ms 8468 KB Output is correct
17 Correct 147 ms 9916 KB Output is correct
18 Correct 143 ms 10192 KB Output is correct
19 Correct 134 ms 8988 KB Output is correct
20 Correct 139 ms 10084 KB Output is correct
21 Correct 124 ms 10236 KB Output is correct
22 Correct 124 ms 10816 KB Output is correct
23 Correct 139 ms 9992 KB Output is correct
24 Correct 152 ms 10460 KB Output is correct
25 Correct 185 ms 19332 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 287 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 224 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -