Submission #1179146


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) {
            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 2694 Byte
Status
Exec Time 430 ms
Memory 17664 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
× 2
× 7
× 23
Set Name Test Cases
Sample sample1.txt, sample2.txt
All 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 15 ms 896 KB
in10.txt 320 ms 17664 KB
in11.txt 329 ms 11732 KB
in12.txt 333 ms 11392 KB
in13.txt 340 ms 11392 KB
in14.txt 338 ms 11648 KB
in15.txt 341 ms 11968 KB
in16.txt 339 ms 11392 KB
in17.txt 348 ms 11392 KB
in18.txt 351 ms 11648 KB
in19.txt 370 ms 11648 KB
in2.txt 15 ms 896 KB
in20.txt 381 ms 12544 KB
in21.txt 347 ms 12044 KB
in22.txt 344 ms 11392 KB
in23.txt 347 ms 13440 KB
in24.txt 361 ms 11648 KB
in25.txt 340 ms 12136 KB
in26.txt 338 ms 11728 KB
in27.txt 348 ms 11392 KB
in28.txt 341 ms 11776 KB
in3.txt 375 ms 11648 KB
in4.txt 361 ms 11648 KB
in5.txt 430 ms 11648 KB
in6.txt 417 ms 11648 KB
in7.txt 294 ms 11008 KB
in8.txt 314 ms 11904 KB
in9.txt 313 ms 14464 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB