Submission #1179177


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;
            no.erase(d);
            dist[p][d] = dist[p][u]+1;
            q.push(d);
        }
    }
}
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]));
        if (deg[i] >= (n-2)/2) {
//            cout << "big " << i << endl;
            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]) {
            if (dist[b][a] >= TEN(8)) {
                cout << -1 << endl;
            } else {
                cout << dist[b][a] << endl;
            }
        } else {
            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 2742 Byte
Status
Exec Time 460 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 16 ms 768 KB
in10.txt 444 ms 17664 KB
in11.txt 384 ms 11732 KB
in12.txt 387 ms 11392 KB
in13.txt 387 ms 11392 KB
in14.txt 387 ms 11648 KB
in15.txt 390 ms 11968 KB
in16.txt 386 ms 11392 KB
in17.txt 396 ms 11392 KB
in18.txt 394 ms 11648 KB
in19.txt 402 ms 11648 KB
in2.txt 16 ms 768 KB
in20.txt 413 ms 12544 KB
in21.txt 390 ms 12044 KB
in22.txt 387 ms 11392 KB
in23.txt 391 ms 11392 KB
in24.txt 393 ms 11648 KB
in25.txt 381 ms 12136 KB
in26.txt 386 ms 11728 KB
in27.txt 399 ms 11392 KB
in28.txt 390 ms 11776 KB
in3.txt 405 ms 11648 KB
in4.txt 385 ms 11648 KB
in5.txt 460 ms 11648 KB
in6.txt 454 ms 11648 KB
in7.txt 346 ms 11008 KB
in8.txt 366 ms 11904 KB
in9.txt 365 ms 14464 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB