제출 #1312033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312033		vladilius	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	0 / 100	1 ms	332 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m; cin>>n>>m;
    
    vector<int> p(n + 1), sz(n + 1);
    for (int i = 1; i <= n; i++){
        p[i] = i;
        sz[i] = 1;
    }
    
    function<int(int)> get = [&](int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    };
    
    set<int> a[n + 1], b[n + 1], c[n + 1];
    
    // b is outgoing
    // c is ingoing
    
    function<void(int, int)> merge = [&](int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        // out -= 1LL * sz[x] * (sz[x] + a[x].size() - 1);
        // out -= 1LL * sz[y] * (sz[y] + a[y].size() - 1);
        
        if (sz[x] < sz[y]) swap(x, y);
        
        p[y] = x;
        sz[x] += sz[y];

        for (int i: a[y]) a[x].insert(i);
        
        vector<int> all;
        for (int i: b[y]){
            if (b[i].find(x) != b[i].end()){
                all.pb(i);
            }
            b[x].insert(i);
        }
        
        for (int i: c[y]){
            if (c[i].find(x) != c[i].end()){
                all.pb(i);
            }
            c[x].insert(i);
        }
        
        assert(a[x].find(x) != a[x].end());
        assert(b[x].find(x) != b[x].end());
        assert(c[x].find(x) != c[x].end());
        assert(a[x].find(y) != a[x].end());
        assert(b[x].find(y) != b[x].end());
        assert(c[x].find(y) != c[x].end());
        a[x].erase(x); a[x].erase(y);
        b[x].erase(x); b[x].erase(y);
        c[x].erase(x); c[x].erase(y);
        
        for (int i: b[x]){
            if (i != get(i)){
                cout<<0 / 0<<"\n";
            }
        }
        
        for (int i: c[x]){
            if (i != get(i)){
                cout<<0 / 0<<"\n";
            }
        }

        // out += 1LL * sz[x] * (sz[x] + a[x].size() - 1);
        
        for (int i: all) merge(x, i);
    };
    
    while (m--){
        int x, y; cin>>x>>y;
        
        int x1 = get(x), y1 = get(y);
        
        if (a[y1].find(x) == a[y1].end()){
            // out += sz[y1];
            a[y1].insert(x);
        }
        
        if (b[y1].find(x1) != b[y1].end()){
            merge(x1, y1);
        }
        else {
            b[x1].insert(y1);
            c[y1].insert(x1);
        }
        
        ll out = 0;
        for (int i = 1; i <= n; i++){
            if (i == get(i)){
                out += 1LL * sz[i] * (sz[i] + a[i].size() - 1);
            }
        }
        
        cout<<out<<"\n";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

joitter2.cpp: In lambda function:
joitter2.cpp:74:25: warning: division by zero [-Wdiv-by-zero]
   74 |                 cout<<0 / 0<<"\n";
      |                       ~~^~~
joitter2.cpp:80:25: warning: division by zero [-Wdiv-by-zero]
   80 |                 cout<<0 / 0<<"\n";
      |                       ~~^~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83