oj.uz

Submission #286324

# Submission time Handle Problem Language Result Execution time Memory
286324 2020-08-30T09:51:21 Z kartel Highway Tolls (IOI18_highway) C++14
51 / 100
 297 ms 262148 KB 
#include <bits/stdc++.h>
//#include "grader.cpp"
#include "highway.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define pb push_back
#define N +100500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define Max_A int(1e9)
//#define el endl
#define pii pair <int, int>
#define piii pair <int, pair <int, int> >
#define psi pair <string, int>
#define err ld(1e-9)
#define Max_S int(3e6)
#define last(x) (x).back()
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

vector <pii> g[N];
ll base;
int ans[2], d[N], D[N];
vi w, lt;

bool gd(int n, int m, int x, ll base)
{
    for (int i = 0; i <= x; i++)
        w[i] = 0;

    for (int i = x + 1; i < m; i++)
        w[i] = 1;
    return (ask(w) == base);
}

int getft(int n, int m)
{
    for (int i = 0; i < m; i++)
        w[i] = 1;

    base = ask(w);

    int l = 0;
    int r = m - 1;
    while (l < r)
    {
        int md = (l + r) >> 1;

        if (gd(n, m, md, base))
            l = md + 1;
        else r = md;
    }

    return l;
}

int getlst(vi lt, int m)
{
    for (int i = 0; i < m; i++) w[i] = 0;
    base = ask(w);

    int l = -1;
    int r = sz(lt) - 1;
    while (l < r)
    {
        int md = (l + r + 1) >> 1;

        for (int i = 0; i < md; i++)
            w[lt[i]] = 0;

        for (int i = md; i < sz(lt); i++)
            w[lt[i]] = 1;

        if (ask(w) != base)
            l = md;
        else r = md - 1;
    }

    return l;
}

void dfs(int v, int pr)
{
    if (pr == -1)
         d[v] = 0;
    else d[v] = d[pr] + 1;

    for (auto u : g[v])
    {
        if (u.F == pr)
            continue;

        dfs(u.F, v);
    }
}

void dfs_0(int v, int pr, int de)
{
    D[v] = de;

    for (auto u : g[v])
    {
        if (u.F == pr)
            continue;

        lt.pb(u.S);
        dfs_0(u.F, v, de + 1);
    }
}

void find_pair(int n, vi u, vi v, int a, int b)
{
    int m = sz(u);

    for (int i = 0; i < m; i++)
    {
        g[u[i]].pb({v[i], i});
        g[v[i]].pb({u[i], i});
    }

    dfs(0, -1);

    w.resize(m);

    int ft = getft(n, m);

    int upper, lower;

    if (d[u[ft]] < d[v[ft]])
         upper = u[ft], lower = v[ft];
    else upper = v[ft], lower = u[ft];

    lt.pb(ft);
    D[lower] = -1;
    dfs_0(upper, lower, 0);

//    for (auto x : lt) cout << x << " ";
//    cout << el;
    int lst = getlst(lt, m);
//    cerr << lst << el;

    if (lst == -1)
        {
            int U = u[lt[0]];
            int V = v[lt[0]];

            if (D[U] > D[V])
                ans[0] = U;
            else ans[0] = V;
        }
    else
    {
        int U = u[lt[lst]];
        int V = v[lt[lst]];

        if (D[U] > D[V])
             ans[0] = U;
        else ans[0] = V;
    }

    lt.clear();
    lt.pb(ft);
    D[upper] = -1;
    dfs_0(lower, upper, 0);

    lst = getlst(lt, m);
//    cerr << lst << el;

    if (lst >= sz(lt))
        {
            int U = u[lt[0]];
            int V = v[lt[0]];

            if (D[U] > D[V])
                ans[1] = U;
            else ans[1] = V;
        }
    else {

        int U = u[lt[lst]];
        int V = v[lt[lst]];

        if (D[U] > D[V])
             ans[1] = U;
        else ans[1] = V;
    }
//    cout << ans[0] << " " << ans[1] << el;

    answer(ans[0], ans[1]);
}

/*int main()
{
    srand(time(0));
    cout.precision(3);
    cout << fixed;
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);


//    in("input.txt");
//    out("output.txt");


}*/

/*
4 4
0110
0000
1101
1100
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 3 ms 2688 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 4 ms 2688 KB Output is correct
2 Correct 18 ms 3456 KB Output is correct
3 Correct 158 ms 9420 KB Output is correct
4 Correct 172 ms 9416 KB Output is correct
5 Correct 151 ms 9564 KB Output is correct
6 Correct 206 ms 9504 KB Output is correct
7 Correct 165 ms 9420 KB Output is correct
8 Correct 148 ms 9564 KB Output is correct
9 Correct 200 ms 9516 KB Output is correct
10 Correct 166 ms 9440 KB Output is correct
11 Correct 169 ms 9816 KB Output is correct
12 Correct 217 ms 10636 KB Output is correct
13 Correct 167 ms 10332 KB Output is correct
14 Correct 206 ms 10284 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3832 KB Output is correct
2 Correct 30 ms 5056 KB Output is correct
3 Correct 55 ms 6376 KB Output is correct
4 Correct 172 ms 12836 KB Output is correct
5 Correct 123 ms 12712 KB Output is correct
6 Correct 140 ms 13232 KB Output is correct
7 Correct 127 ms 14176 KB Output is correct
8 Correct 126 ms 12888 KB Output is correct
9 Correct 130 ms 12836 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 19 ms 3328 KB Output is correct
3 Correct 110 ms 7984 KB Output is correct
4 Correct 154 ms 9532 KB Output is correct
5 Correct 164 ms 9432 KB Output is correct
6 Correct 146 ms 9432 KB Output is correct
7 Correct 146 ms 9436 KB Output is correct
8 Correct 144 ms 9404 KB Output is correct
9 Correct 150 ms 9436 KB Output is correct
10 Correct 161 ms 9412 KB Output is correct
11 Correct 174 ms 10052 KB Output is correct
12 Correct 220 ms 10692 KB Output is correct
13 Correct 211 ms 10324 KB Output is correct
14 Correct 165 ms 10132 KB Output is correct
15 Correct 196 ms 9416 KB Output is correct
16 Correct 143 ms 9436 KB Output is correct
17 Correct 210 ms 10100 KB Output is correct
18 Correct 208 ms 10540 KB Output is correct
19 Correct 193 ms 9432 KB Output is correct
20 Correct 188 ms 10996 KB Output is correct
21 Correct 169 ms 9616 KB Output is correct
22 Correct 154 ms 9712 KB Output is correct
23 Correct 135 ms 9224 KB Output is correct
24 Correct 189 ms 9620 KB Output is correct
25 Correct 166 ms 13688 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 297 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 280 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -