Submission #1033786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033786		vjudge1	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	0 / 100	3 ms	5212 KiB

timeleap

#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second

using namespace std;

const int mod = 1e9 + 7;
const int N = 1e5 + 5;

int n, m, deg[N], U[2 * N], V[2 * N];
vector <int> c[N];
int ans[2 * N], cnt[N];
int d[N], used[N], timer;

void bfs(int u){
    int gg = u;
    queue <int> q;
    vector <int> re, nw;
    for (int i = 1; i <= n; ++ i) if (u != i) re.push_back(i), d[i] = -1;
    q.push(u);
    d[u] = 0;
    while (!q.empty()){
        u = q.front();
        q.pop();
        timer ++;
        for (int i : c[u]){
            int v = U[i] ^ V[i] ^ u;
            used[v] = timer;
        }

        for (int i : re){
            if (used[i] != timer) {
                d[i] = d[u] + 1;
                q.push(i);
            }
            else nw.push_back(i);
        }
        swap(re, nw);
        nw.clear();
    }

    for (int i : c[gg]) {
        int v = U[i] ^ V[i] ^ gg;
        ans[i] = d[v];
    }
}

void solve(){
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i){
        cin >> U[i] >> V[i];
        deg[U[i]] ++;
        deg[V[i]] ++;
        c[U[i]].push_back(i);
        c[V[i]].push_back(i);
    }

    for (int i = 1; i <= n; ++ i) if (deg[i] >= n / 2) bfs(i);

    for (int i = 1; i <= m; ++ i) {
        if (ans[i] == 0) cnt[2] ++;
        else if (ans[i] != -1) cnt[ans[i]] ++;
    }

    cout << 1ll * n * (n - 1) / 2 - m << ' ';
    for (int i = 2; i < n; ++ i) cout << cnt[i] << ' ';
}

int main(){
    //freopen("code.inp", "r", stdin);
    //freopen("code.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t --) solve();

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 30
• Subtask 3: 0 / 66