Submission #1179241


Source Code Expand

Copy
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(uint x) { return 31 - __builtin_clz(x); }
int bsr(ull x) { return 63 - __builtin_clzll(x); }
int bsf(uint x) { return __builtin_ctz(x); }
int bsf(ull x) { return __builtin_ctzll(x); }

using P = pair<int, int>;
int n, m;
VV<int> g;
V<int> deg;
V<set<int>> g_set;

set<P> edges;
V<bool> is_big;
VV<int> dist;

bool have(int a, int b) {
    return binary_search(begin(g[a]), end(g[a]), b);
}

void naive(int p) {
    dist[p] = V<int>(n, TEN(9));
    dist[p][p] = 0;
    queue<int> q;
    set<int> no;
    for (int i = 0; i < n; i++) {
        no.insert(i);
    }
    q.push(p);
    no.erase(p);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        auto it = no.begin();
        while (it != no.end()) {
            int d = *it; it++;
            if (have(u, d)) continue;

            assert(dist[p][d] == TEN(9));
            no.erase(d);
            q.push(d);
            dist[p][d] = dist[p][u]+1;
        }
    }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20);
    int q;
    cin >> n >> m >> q;
    g = VV<int>(n);
    deg = V<int>(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        edges.insert(P(a, b));
        edges.insert(P(b, a));
        g[a].push_back(b);
        g[b].push_back(a);
        deg[a]++; deg[b]++;
    }
    is_big = V<bool>(n);
    dist = VV<int>(n);
    for (int i = 0; i < n; i++) {
        sort(begin(g[i]), end(g[i]));        
    }
    for (int i = 0; i < n; i++) {
        if (deg[i] >= (n-2)/2) {
            is_big[i] = true;
            naive(i);
        }
    }
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        if (deg[a] > deg[b]) swap(a, b);
        if (is_big[b]) {
            assert(dist[b].size());
            if (dist[b][a] >= TEN(8)) {
                cout << -1 << endl;
            } else {
                cout << dist[b][a] << endl;
            }
        } else {
            assert(!is_big[a]);
            if (edges.count(P(a, b))) {
                cout << 2 << endl;
            } else {
                cout << 1 << endl;
            }
        }
    }
    return 0;
}

Submission Info

Submission Time
Task E - 瞬間移動装置
User yosupo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2863 Byte
Status
Exec Time 2104 ms
Memory 17664 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt
All 0 / 1400 in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt
Case Name Status Exec Time Memory
in1.txt 23 ms 896 KB
in10.txt 359 ms 17664 KB
in11.txt 360 ms 11732 KB
in12.txt 413 ms 13184 KB
in13.txt 460 ms 11392 KB
in14.txt 520 ms 11648 KB
in15.txt 429 ms 11968 KB
in16.txt 534 ms 11392 KB
in17.txt 606 ms 11392 KB
in18.txt 659 ms 11648 KB
in19.txt 2104 ms 11392 KB
in2.txt 24 ms 768 KB
in20.txt 395 ms 12544 KB
in21.txt 455 ms 12040 KB
in22.txt 511 ms 11392 KB
in23.txt 617 ms 11392 KB
in24.txt 653 ms 11648 KB
in25.txt 353 ms 12092 KB
in26.txt 368 ms 11712 KB
in27.txt 384 ms 11392 KB
in28.txt 369 ms 11776 KB
in3.txt 1705 ms 11648 KB
in4.txt 1309 ms 11648 KB
in5.txt 576 ms 11648 KB
in6.txt 562 ms 11648 KB
in7.txt 321 ms 11008 KB
in8.txt 343 ms 11904 KB
in9.txt 347 ms 14592 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB