oj.uz

답안 #978993

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
978993 2024-05-10T05:37:44 Z The_Samurai 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 1 ms 600 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

ll get(int l, int r = -1) {
    if (r == -1) return 1ll * l * (l + 1) / 2;
    return 1ll * (r - l + 1) * (l + r) / 2;
}

void solve() {
    int n, m;
    cin >> n >> m;
    ll ans = 0;
    vector<vector<int>> have(n + 1);
    vector<set<int>> in(n + 1), out(n + 1);
    set<pair<int, int>> adj;
    vector<int> weight(n + 1, 2), par(n + 1);
    for (int i = 1; i <= n; i++) have[i].emplace_back(i);
    iota(par.begin(), par.end(), 0);
    while (m--) {
        int u, v;
        cin >> u >> v;
        if (par[u] == par[v] or out[u].count(par[v])) {
            cout << ans << '\n';
            continue;
        }
        if (adj.count(make_pair(par[v], par[u]))) {
            u = par[u], v = par[v];
            adj.erase(make_pair(v, u));
            if (weight[u] < weight[v]) swap(u, v);
            ans -= 1ll * have[u].size() * (have[u].size() - 1);
            ans -= 1ll * have[v].size() * (have[v].size() - 1);
            for (int x: in[u]) {
                ans -= have[u].size();
            }
            weight[u] -= have[u].size() + in[u].size();
            // cout << u << ' ' << v << endl;
            for (int x: in[v]) {
                ans -= have[v].size();
                if (par[x] == u) continue;
                
                in[u].insert(x);

                out[x].erase(v);
                out[x].insert(u);

                if (adj.count(make_pair(par[x], v))) adj.erase(make_pair(par[x], v));
                adj.emplace(par[x], u);

                out[x].erase(v);
                out[x].insert(u);
            }
            int old = have[u].size();
            for (int x: have[v]) {
                par[x] = u;
                have[u].emplace_back(x);
                vector<int> del;
                for (int y: out[x]) if (y == u) del.emplace_back(y), in[u].erase(x);
                for (int y: del) out[x].erase(y);
                weight[u] += out[x].size();
            }
            weight[u] += have[u].size() + in[u].size();
            // cout << '\t';
            // for (int x: in[u]) cout << x << ' ';
            // cout << endl;
            for (int x: in[u]) ans += have[u].size();
            ans += have[u].size() * (have[u].size() - 1);
            in[v].clear(), have[v].clear();
        } else {
            ans += have[par[v]].size();
            out[u].insert(par[v]);
            in[par[v]].insert(u);
            weight[par[u]]++, weight[par[v]]++;
            adj.emplace(par[u], par[v]);
        }
        cout << ans << '\n';
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int queries = 1;

#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    // cin >> queries;

    for (int test_case = 1; test_case <= queries; test_case++) {
#ifdef sunnatov
        cout << "Test case: " << test_case << endl;
#endif
        solve();
        cout << '\n';
    }
}

Compilation message

joitter2.cpp: In function 'void solve()':
joitter2.cpp:33:22: warning: unused variable 'x' [-Wunused-variable]
   33 |             for (int x: in[u]) {
      |                      ^
joitter2.cpp:66:22: warning: unused variable 'x' [-Wunused-variable]
   66 |             for (int x: in[u]) ans += have[u].size();
      |                      ^
joitter2.cpp:53:17: warning: unused variable 'old' [-Wunused-variable]
   53 |             int old = have[u].size();
      |                 ^~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Incorrect 1 ms 600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Incorrect 1 ms 600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Incorrect 1 ms 600 KB Output isn't correct
4 Halted 0 ms 0 KB -