제출 #212784

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

joitter2

#define DBG 1
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) if (DBG) cerr << #x << " = " << x << endl;

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = 55;

int par[MAXN], sz[MAXN];
set<int> adj[MAXN];
set<pii> e;
int n, m;

int getPar(int x) {
    if (x == par[x]) {
        return x;
    }
    
    return par[x] = getPar(par[x]);
}

void uni(int a, int b) {
    a = getPar(a);
    b = getPar(b);
    
    if (a != b) {
        sz[a] += sz[b];
        par[b] = a;
    }
}

void compress() {
    set<pii> e2;
 
    for (auto it : e) {
        int u = it.fi;
        int v = it.se;
        u = getPar(u);
        v = getPar(v);
        
        if (u != v) {
            e2.insert(mp(u, v));
        }
    }
    
    e = e2;
    
    for (int i = 1; i <= n; ++i) {
        set<int> s;
        
        for (int x : adj[i]) {
            x = getPar(x);
            
            if (x != getPar(i)) {
                s.insert(x);
            }
        }
        
        adj[i] = s;
    }
}

void push() {
    bool did = 1;

    while (did) {
        compress();
        did = 0;
    
        for (auto it : e) {
            if (e.find(mp(it.se, it.fi)) != e.end()) {
                uni(it.fi, it.se);
                did = 1;
            }
        }
        
        compress();
    }
}

void solve() {
	scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; ++i) {
        par[i] = i;
        sz[i] = 1;
    }
    
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].insert(v);
        u = getPar(u);
        v = getPar(v);
        e.insert(mp(u, v));
        
        if (e.find(mp(v, u)) != e.end()) {
            uni(u, v);
        }
    
        push();
        compress();
        ll ans = 0;
        
        for (int j = 1; j <= n; ++j) {
            if (par[j] == j) {
                ans += sz[j] * (sz[j] - 1ll);
            }
        }
        
        for (int j = 1; j <= n; ++j) {
            for (int x : adj[j]) {
                ans += sz[x];
            }
        }
        
        printf("%lld\n", ans);
    }
}

int main() {
	int tt = 1;
	
	while (tt--) {
		solve();
	}

	return 0;
}

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

joitter2.cpp: In function 'void solve()':
joitter2.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

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