oj.uz

Submission #316886

# Submission time Handle Problem Language Result Execution time Memory
316886 2020-10-28T12:40:06 Z anakib1 Highway Tolls (IOI18_highway) C++17
51 / 100
 219 ms 17752 KB 
//나는 가상 소녀들에게 큰 호감이 있습니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <chrono>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <deque>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdarg.h>
#include <utility>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unisgned long long
#define ld long double
#define all(a) a.begin(), a.end()
#define SORT(a) sort(all(a))
#define pii pair<int, int>
#define tii triple<int, int, int>
#define e 1e-7
#define PI acos(-1)
#define sz(a) (int)(a.size())
#define inf 1e17
#define vi vector<int>
#define F first
#define S second
#define rng(x) for(int _ = 0; _ < (x); _++)
#define rngi(i, x) for(int i = 0; i < (x); i++)
#define rngsi(s, i, x) for(int i = (s); i <(x); i++)
#define problem "a"
#pragma comment(linker, "/STACK:36777216")


template<typename A, typename B, typename C>
struct triple {
    A X;
    B Y;
    C Z;
    triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
};
template<typename A, typename B, typename C>
triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0) {
    return triple<A, B, C>(a, b, c);
}
template<typename A, typename B, typename C>
bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b) {
    if (a.X != b.X)
        return a.X < b.X;
    if (a.Y != b.Y)
        return a.Y < b.Y;
    return a.Z < b.Z;
}
template<typename T, typename SS>
ostream& operator<<(ostream& ofs, const pair<T, SS>& p) {
    ofs << "( " << p.F << " , " << p.S << " )";
    return ofs;
}
template<typename T>
void print(T a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
template<typename T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}
template<typename T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}
template<typename T, typename D>
D min(T a) {
    return *min_element(all(a));
}
template<typename T, typename D>
D max(T a) {
    return *max_element(all(a));
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#include "highway.h"
vector<vi> idlevel; int mxh = 0;
vector<vi> ids;
vector<vector<pii> > g;
vi pe;
vi usd;
void dfs(int v, int p, int h) {
    queue<tii> q;
    q.push({ v,p,h });
    while (sz(q)) {
        auto xx = q.front(); q.pop();
        v = xx.X, p = xx.Y, h = xx.Z;

        usd[v] = 1;
        mxh = max(mxh, h);
        ids[h].push_back(v);
        for (auto to : g[v]) if (!usd[to.first]) {
            idlevel[h].push_back(to.second);
            pe[to.first] = to.second;
            q.push({ to.first, v, h + 1 });
        }
    }
}

void find_pair(int n, std::vector<int> u, std::vector<int> v, int a, int b) {
    g.resize(n);
    int mm = sz(u), m;
    rngi(i, mm) g[u[i]].push_back({ v[i],i }), g[v[i]].push_back({ u[i],i });
    idlevel.assign(n, vi());
    ids.assign(n, vi());
    pe.assign(n, 0);
    mxh = 0;
    usd.assign(n, 0);
    dfs(0, 0, 0);
    ll reg = ask(vi(mm, 0));
    int l = 0, r = mxh + 1;
    map<int, bool> memo;
    auto ok = [&](int x) {
        if (x >= mxh) return false;
        if (memo.count(x)) return memo[x];
        vi w(mm);
        for(int i = x; i < mxh; i++)for (auto v : idlevel[i]) w[v] = 1;
        ll ans = ask(w);
        return memo[x] = (ans > reg);
    };
    while (r - l > 1) {
        m = l + r >> 1;
        if (ok(m)) l = m; else r = m;
    }
    int lca = l; if (ok(r)) lca = r;
    memo.clear();
    l = 0, r = sz(ids[lca + 1]);
    auto ok2 = [&](int x) {
        if (x == sz(ids[lca + 1])) return false;
        if (memo.count(x)) return memo[x];
        vi w(mm);
        rngi(i, x + 1) w[pe[ids[lca + 1][i]]] = 1;
        ll ans = ask(w);
        return memo[x] = (ans > reg);
    };
    while (r - l > 1) {
        m = l + r >> 1;
        if (ok2(m)) r = m; else l = m;
    }
    int id = r; if (ok2(l)) id = l;
    int s = ids[lca + 1][id];
    idlevel.assign(n, vi());
    ids.assign(n, vi());
    pe.assign(n, 0);
    usd.assign(n, 0);
    mxh = 0;
    dfs(s, s, 0);
    l = 0, r = mxh + 1;
    memo.clear();
    while (r - l > 1) {
        m = l + r >> 1;
        if (ok(m)) l = m; else r = m;
    }
    lca = l; if (ok(r)) lca = r;
    l = 0, r = sz(ids[lca + 1]);
    memo.clear();
    while (r - l > 1) {
        m = l + r >> 1;
        if (ok2(m)) r = m; else l = m;
    }
    id = r; if (ok2(l)) id = l;
  //  cout << lca << '\n';
  //  rngi(i, mxh) print(ids[i]);
    //print(ids[lca + 1]);
    answer(s, ids[lca + 1][id]);
}
/*
9 8 1 2 2 5
0 1 0 2 1 3 3 8 3 4 3 6 6 5 8 7
*/

Compilation message

highway.cpp:52: warning: ignoring #pragma comment  [-Wunknown-pragmas]
   52 | #pragma comment(linker, "/STACK:36777216")
      | 
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:160:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |         m = l + r >> 1;
      |             ~~^~~
highway.cpp:175:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  175 |         m = l + r >> 1;
      |             ~~^~~
highway.cpp:189:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  189 |         m = l + r >> 1;
      |             ~~^~~
highway.cpp:196:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  196 |         m = l + r >> 1;
      |             ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 15 ms 1792 KB Output is correct
3 Correct 219 ms 13888 KB Output is correct
4 Correct 216 ms 13844 KB Output is correct
5 Correct 177 ms 13876 KB Output is correct
6 Correct 174 ms 13820 KB Output is correct
7 Correct 178 ms 14188 KB Output is correct
8 Correct 166 ms 14244 KB Output is correct
9 Correct 173 ms 14340 KB Output is correct
10 Correct 177 ms 14000 KB Output is correct
11 Correct 190 ms 14172 KB Output is correct
12 Correct 202 ms 14500 KB Output is correct
13 Correct 203 ms 13904 KB Output is correct
14 Correct 192 ms 14396 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2304 KB Output is correct
2 Correct 34 ms 4216 KB Output is correct
3 Correct 46 ms 6136 KB Output is correct
4 Correct 152 ms 17692 KB Output is correct
5 Correct 155 ms 17668 KB Output is correct
6 Correct 140 ms 17752 KB Output is correct
7 Correct 149 ms 17660 KB Output is correct
8 Correct 151 ms 17656 KB Output is correct
9 Correct 149 ms 17664 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 528 KB Output is correct
2 Correct 16 ms 1912 KB Output is correct
3 Correct 123 ms 11280 KB Output is correct
4 Correct 162 ms 13852 KB Output is correct
5 Correct 161 ms 13488 KB Output is correct
6 Correct 165 ms 13912 KB Output is correct
7 Correct 164 ms 13888 KB Output is correct
8 Correct 159 ms 13612 KB Output is correct
9 Correct 169 ms 13788 KB Output is correct
10 Correct 162 ms 13908 KB Output is correct
11 Correct 187 ms 14016 KB Output is correct
12 Correct 176 ms 14668 KB Output is correct
13 Correct 182 ms 14028 KB Output is correct
14 Correct 192 ms 14528 KB Output is correct
15 Correct 157 ms 13744 KB Output is correct
16 Correct 157 ms 14264 KB Output is correct
17 Correct 184 ms 14344 KB Output is correct
18 Correct 216 ms 14332 KB Output is correct
19 Correct 214 ms 13968 KB Output is correct
20 Correct 191 ms 14828 KB Output is correct
21 Correct 204 ms 14748 KB Output is correct
22 Correct 171 ms 14768 KB Output is correct
23 Correct 171 ms 14376 KB Output is correct
24 Correct 191 ms 14372 KB Output is correct
25 Correct 199 ms 17500 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2040 KB Output is correct
2 Correct 20 ms 2192 KB Output is correct
3 Incorrect 213 ms 15096 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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