제출 #330534

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

joitter2

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n,q;
set<int> g[maxn];


void add_edge(int u, int v) {
    g[u].insert(v);
}


void relax() {
    while (true) {
	bool ok = false;
	for (int x=0; x<n && !ok; x++) {
	    for (int y: g[x]) {
		if (ok) break;
		for (int z: g[y]) {
		    if (g[z].count(y) && !g[x].count(z) && x!=z) {
			g[x].insert(z);
			ok = true;
			break;
		    }
		}
	    }
	}

	if (!ok) break;
    }
}


ll count() {
    ll res = 0;
    for (int i=0; i<n; i++) {
	res += g[i].size();
    }


    // for (int i=0; i<n; i++) {
    // 	for (int j: g[i]) {
    // 	    cout<<i+1<<"->"<<j+1<<endl;
    // 	}
    // }
    
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>q;
    while (q--) {
	int u,v;
	cin>>u>>v;
	--u; --v;
	add_edge(u,v);
	relax();
	cout<<count()<<"\n";
    }
    
    
    return 0;
}

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