Submission #316891

#	Time	Username	Problem	Language	Result	Execution time	Memory
316891		anakib1	Highway Tolls (IOI18_highway)	C++17	51 / 100	1004 ms	22004 KiB

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;
set<int> intree;

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]) {
            usd[to.first] = 1;
            idlevel[h].push_back(to.second);
            pe[to.first] = to.second;
            q.push({ to.first, v, h + 1 });
            intree.insert(to.second);
        }
    }
}
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);
    int vv = 0; 
    ll reg = ask(vi(mm, 0));
    auto gen = [&]() {
        vi ans(mm);
        rngi(i, mm) if (!intree.count(i)) ans[i] = 1;
        return ans;
    };
    map<int, bool> memo;
    if (n != mm + 1) {
        auto ok = [&](int x) {
            if (x == n)return true;
            if (memo.count(x)) return memo[x];
            vi w(mm);
            rngi(i, x + 1) for (auto v : g[i]) w[v.second] = 1;
            ll ans = ask(w);
            return memo[x] = (ans > reg);
        };
        int l = 0, r = n;
        while (r - l > 1) {
            m = l + r >> 1;
            if (ok(m)) r = m; else l = m;
        }
        vv = r; if (ok(l)) vv = l;
    }
    dfs(vv, vv, 0);
    int l = 0, r = mxh + 1;
    memo.clear();
    auto ok = [&](int x) {
        if (x >= mxh) return false;
        if (memo.count(x)) return memo[x];
        vi w = gen();
        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 = gen();
        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;
    intree.clear();
    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;
 //   rngi(i, mxh) if (count(all(ids[i]), 6594)) cout << i << '\n';
  //  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 (stderr)

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:169:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |             m = l + r >> 1;
      |                 ~~^~~
highway.cpp:186:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  186 |         m = l + r >> 1;
      |             ~~^~~
highway.cpp:201:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  201 |         m = l + r >> 1;
      |             ~~^~~
highway.cpp:216:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  216 |         m = l + r >> 1;
      |             ~~^~~
highway.cpp:223:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  223 |         m = l + r >> 1;
      |             ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31