oj.uz

답안 #316877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
316877 2020-10-28T11:58:18 Z anakib1 통행료 (IOI18_highway) C++17
51 / 100
 206 ms 17772 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 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 1920 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 1920 KB Incorrect
2 Halted 0 ms 0 KB -