oj.uz

Submission #330534

# Submission time Handle Problem Language Result Execution time Memory
330534 2020-11-25T16:54:44 Z limabeans Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 5000 ms 47596 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47340 KB Output is correct
2 Correct 29 ms 47340 KB Output is correct
3 Correct 30 ms 47340 KB Output is correct
4 Correct 30 ms 47340 KB Output is correct
5 Correct 32 ms 47340 KB Output is correct
6 Correct 31 ms 47340 KB Output is correct
7 Execution timed out 5094 ms 47596 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47340 KB Output is correct
2 Correct 29 ms 47340 KB Output is correct
3 Correct 30 ms 47340 KB Output is correct
4 Correct 30 ms 47340 KB Output is correct
5 Correct 32 ms 47340 KB Output is correct
6 Correct 31 ms 47340 KB Output is correct
7 Execution timed out 5094 ms 47596 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47340 KB Output is correct
2 Correct 29 ms 47340 KB Output is correct
3 Correct 30 ms 47340 KB Output is correct
4 Correct 30 ms 47340 KB Output is correct
5 Correct 32 ms 47340 KB Output is correct
6 Correct 31 ms 47340 KB Output is correct
7 Execution timed out 5094 ms 47596 KB Time limit exceeded
8 Halted 0 ms 0 KB -