Submission #316877

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
316877	2020-10-28T11:58:18 Z	anakib1	Highway Tolls (IOI18_highway)	C++17	51 / 100	206 ms	17772 KB

highway

//나는 가상 소녀들에게 큰 호감이 있습니다.

#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 m = sz(u);
    rngi(i, m) 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(n - 1, 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(n - 1);
        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(n - 1);
        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	256 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	180 ms	13836 KB	Output is correct
4	Correct	172 ms	13916 KB	Output is correct
5	Correct	170 ms	13884 KB	Output is correct
6	Correct	157 ms	13812 KB	Output is correct
7	Correct	177 ms	14192 KB	Output is correct
8	Correct	168 ms	14144 KB	Output is correct
9	Correct	169 ms	14456 KB	Output is correct
10	Correct	171 ms	13932 KB	Output is correct
11	Correct	186 ms	14144 KB	Output is correct
12	Correct	199 ms	14488 KB	Output is correct
13	Correct	196 ms	13896 KB	Output is correct
14	Correct	193 ms	14412 KB	Output is correct

Subtask #3

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2304 KB	Output is correct
2	Correct	33 ms	4224 KB	Output is correct
3	Correct	47 ms	6136 KB	Output is correct
4	Correct	152 ms	17768 KB	Output is correct
5	Correct	155 ms	17764 KB	Output is correct
6	Correct	149 ms	17772 KB	Output is correct
7	Correct	149 ms	17664 KB	Output is correct
8	Correct	146 ms	17656 KB	Output is correct
9	Correct	146 ms	17656 KB	Output is correct

Subtask #4

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	512 KB	Output is correct
2	Correct	15 ms	1920 KB	Output is correct
3	Correct	125 ms	11296 KB	Output is correct
4	Correct	166 ms	13800 KB	Output is correct
5	Correct	157 ms	13484 KB	Output is correct
6	Correct	166 ms	13996 KB	Output is correct
7	Correct	155 ms	13900 KB	Output is correct
8	Correct	164 ms	13608 KB	Output is correct
9	Correct	169 ms	13788 KB	Output is correct
10	Correct	175 ms	13836 KB	Output is correct
11	Correct	202 ms	14016 KB	Output is correct
12	Correct	186 ms	14744 KB	Output is correct
13	Correct	195 ms	14068 KB	Output is correct
14	Correct	196 ms	14380 KB	Output is correct
15	Correct	172 ms	13736 KB	Output is correct
16	Correct	161 ms	14220 KB	Output is correct
17	Correct	187 ms	14368 KB	Output is correct
18	Correct	200 ms	14484 KB	Output is correct
19	Correct	168 ms	13880 KB	Output is correct
20	Correct	195 ms	14756 KB	Output is correct
21	Correct	153 ms	14704 KB	Output is correct
22	Correct	173 ms	14748 KB	Output is correct
23	Correct	175 ms	14216 KB	Output is correct
24	Correct	193 ms	14360 KB	Output is correct
25	Correct	206 ms	17396 KB	Output is correct

Subtask #5

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	14 ms	1920 KB	Incorrect
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	14 ms	1920 KB	Incorrect
2	Halted	0 ms	0 KB	-