Submission #1179275


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);
}

struct FastSet {
    int N, lg;
    VV<ull> seg;
    FastSet(int N) : N(N) {
        while (N > 1) {
            seg.push_back(V<ull>((N+63)/64));
            N = (N+63)/64;
        }
        lg = seg.size();
    }
    bool test(int x) const {
        int D = x/64, R = x%64;
        return (seg[0][D] & (1ULL<<R)) != 0;
    }
    void set(int x) {
        for (int i = 0; i < lg; i++) {
            int D = x/64, R = x%64;
            seg[i][D] |= (1ULL<<R);
            x /= 64;
        }
    }
    void clear(int x) {
        for (int i = 0; i < lg; i++) {
            int D = x/64, R = x%64;
            seg[i][D] &= ~(1ULL<<R);
            if (i && seg[i-1][x] != 0) {
                seg[i][D] |= (1ULL<<R);
            }
            x /= 64;
        }
    }
    // x以上最小の要素
    int next(int x) {
        for (int i = 0; i < lg; i++) {
            int D = x/64, R = x%64;
            if (D == seg[i].size()) break;
            ull B = seg[i][D]>>R;
            if (!B) {
                x = x/64+1;
                continue;
            }
            //find
            x += bsf(B);
            for (int j = i-1; j >= 0; j--) {
                x *= 64;
                int D = x/64;
                x += bsf(seg[j][D]);
            }
            return x;
        }
        return N;
    }
    // x以下最大の要素
    int back(int x) {
        for (int i = 0; i < lg; i++) {
            if (x == -1) break;
            int D = x/64, R = x%64;
            ull B = seg[i][D]<<(63-R);
            if (!B) {
                x = x/64-1;
                continue;
            }
            //find
            x += bsr(B)-63;
            for (int j = i-1; j >= 0; j--) {
                x *= 64;
                int D = x/64;
                x += bsr(seg[j][D]);
            }
            return x;
        }
        return -1;
    }    
};

void naive(int p) {
    dist[p] = V<int>(n, TEN(9));
    dist[p][p] = 0;
    queue<int> q;
//    set<int> no;
    FastSet no(n);
    for (int i = 0; i < n; i++) {
        no.set(i);
//        no.insert(i);
    }
    q.push(p);
    no.clear(p);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        int ba = 0;
        while (ba < n) {
            int d = no.next(ba);
            if (d == n) break;
            
            ba = d+1;
            if (have(u, d)) continue;
            assert(dist[p][d] == TEN(9));
            no.clear(d);
            q.push(d);
            dist[p][d] = dist[p][u]+1;
        }
    }
}
int main() {
    int q;
    scanf("%d %d %d", &n, &m, &q);
    g = VV<int>(n);
    deg = V<int>(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &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]));        
    }

    //ok
    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;
        scanf("%d %d", &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)) {
                printf("-1\n");
            } else {
                printf("%d\n", dist[b][a]);
            }
        } else {
            assert(!is_big[a]);
            if (edges.count(P(a, b))) {
                printf("2\n");
            } else {
                printf("1\n");
            }
        }
    }
    return 0;
}

Submission Info

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

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:150:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
                                  ^
./Main.cpp:155:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b); a--; b--;
                               ^
./Main.cpp:177:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b); a--; b--;
                               ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1400 / 1400
Status
× 2
× 30
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 12 ms 768 KB
in10.txt 223 ms 17664 KB
in11.txt 232 ms 11648 KB
in12.txt 240 ms 11264 KB
in13.txt 291 ms 11264 KB
in14.txt 345 ms 11648 KB
in15.txt 286 ms 11776 KB
in16.txt 346 ms 11264 KB
in17.txt 384 ms 11264 KB
in18.txt 416 ms 11648 KB
in19.txt 1654 ms 11648 KB
in2.txt 13 ms 768 KB
in20.txt 207 ms 12544 KB
in21.txt 280 ms 11904 KB
in22.txt 324 ms 11264 KB
in23.txt 381 ms 11264 KB
in24.txt 399 ms 11648 KB
in25.txt 208 ms 11776 KB
in26.txt 198 ms 11520 KB
in27.txt 221 ms 11264 KB
in28.txt 216 ms 11648 KB
in3.txt 1158 ms 11648 KB
in4.txt 884 ms 11520 KB
in5.txt 356 ms 11648 KB
in6.txt 342 ms 11648 KB
in7.txt 164 ms 11008 KB
in8.txt 196 ms 11904 KB
in9.txt 208 ms 14464 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB