oj.uz

Submission #939337

# Submission time Handle Problem Language Result Execution time Memory
939337 2024-03-06T09:27:17 Z WonderfulWhale Making Friends on Joitter is Fun (JOI20_joitter2) C++17
1 / 100
 5000 ms 11308 KB 
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int MAXN = 100'009;

int p[MAXN];
int sz[MAXN];
set<int> M[MAXN];
set<pii> S;

int Find(int x) {
	return x==p[x]?x:p[x]=Find(p[x]);
}

void Union(int a, int b) {
	p[Find(a)] = Find(b);
}

int tab[1009][1009];
int tab2[1009][1009];
int ans = 0;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	int n, m;
	cin >> n >> m;
	for(int i=0;i<m;i++) {
		int a, b;
		cin >> a >> b;
		tab[a][b] = true;
		for(int j=1;j<=n;j++) {
			for(int k=1;k<=n;k++) {
				tab2[j][k] = tab[j][k];
			}
		}
		int ans = 0;
		//cerr << "New\n";
		while(true) {
			bool yes = false;
			for(int a=1;a<=n;a++) {
				for(int b=1;b<=n;b++) {
					for(int c=1;c<=n;c++) {
						if(a==c) continue;
						if(tab2[a][b]&&!tab2[a][c]&&tab2[b][c]&&tab2[c][b]) {
							tab2[a][c] = true;
							ans++;
							yes = true;
							//cerr << "adding: " << a << " " << c << "\n";
						}
					}
				}
			}
			if(!yes) break;
		}
		cout << i+1+ans << "\n";
	}
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8716 KB Output is correct
7 Correct 1146 ms 10820 KB Output is correct
8 Correct 1125 ms 10844 KB Output is correct
9 Correct 1105 ms 10840 KB Output is correct
10 Correct 53 ms 10584 KB Output is correct
11 Correct 28 ms 10584 KB Output is correct
12 Correct 30 ms 10588 KB Output is correct
13 Correct 27 ms 10588 KB Output is correct
14 Correct 26 ms 10584 KB Output is correct
15 Correct 27 ms 10584 KB Output is correct
16 Correct 52 ms 10584 KB Output is correct
17 Correct 50 ms 10584 KB Output is correct
18 Correct 36 ms 10588 KB Output is correct
19 Correct 36 ms 10584 KB Output is correct
20 Correct 170 ms 10588 KB Output is correct
21 Correct 1063 ms 10820 KB Output is correct
22 Correct 195 ms 10804 KB Output is correct
23 Correct 591 ms 10584 KB Output is correct
24 Correct 303 ms 10812 KB Output is correct
25 Correct 971 ms 10820 KB Output is correct
26 Correct 13 ms 10584 KB Output is correct
27 Correct 13 ms 10588 KB Output is correct
28 Correct 16 ms 10588 KB Output is correct
29 Correct 17 ms 10588 KB Output is correct
30 Correct 33 ms 10728 KB Output is correct
31 Correct 900 ms 10588 KB Output is correct
32 Correct 42 ms 10588 KB Output is correct
33 Correct 1008 ms 10828 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8716 KB Output is correct
7 Correct 1146 ms 10820 KB Output is correct
8 Correct 1125 ms 10844 KB Output is correct
9 Correct 1105 ms 10840 KB Output is correct
10 Correct 53 ms 10584 KB Output is correct
11 Correct 28 ms 10584 KB Output is correct
12 Correct 30 ms 10588 KB Output is correct
13 Correct 27 ms 10588 KB Output is correct
14 Correct 26 ms 10584 KB Output is correct
15 Correct 27 ms 10584 KB Output is correct
16 Correct 52 ms 10584 KB Output is correct
17 Correct 50 ms 10584 KB Output is correct
18 Correct 36 ms 10588 KB Output is correct
19 Correct 36 ms 10584 KB Output is correct
20 Correct 170 ms 10588 KB Output is correct
21 Correct 1063 ms 10820 KB Output is correct
22 Correct 195 ms 10804 KB Output is correct
23 Correct 591 ms 10584 KB Output is correct
24 Correct 303 ms 10812 KB Output is correct
25 Correct 971 ms 10820 KB Output is correct
26 Correct 13 ms 10584 KB Output is correct
27 Correct 13 ms 10588 KB Output is correct
28 Correct 16 ms 10588 KB Output is correct
29 Correct 17 ms 10588 KB Output is correct
30 Correct 33 ms 10728 KB Output is correct
31 Correct 900 ms 10588 KB Output is correct
32 Correct 42 ms 10588 KB Output is correct
33 Correct 1008 ms 10828 KB Output is correct
34 Execution timed out 5057 ms 11308 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8716 KB Output is correct
7 Correct 1146 ms 10820 KB Output is correct
8 Correct 1125 ms 10844 KB Output is correct
9 Correct 1105 ms 10840 KB Output is correct
10 Correct 53 ms 10584 KB Output is correct
11 Correct 28 ms 10584 KB Output is correct
12 Correct 30 ms 10588 KB Output is correct
13 Correct 27 ms 10588 KB Output is correct
14 Correct 26 ms 10584 KB Output is correct
15 Correct 27 ms 10584 KB Output is correct
16 Correct 52 ms 10584 KB Output is correct
17 Correct 50 ms 10584 KB Output is correct
18 Correct 36 ms 10588 KB Output is correct
19 Correct 36 ms 10584 KB Output is correct
20 Correct 170 ms 10588 KB Output is correct
21 Correct 1063 ms 10820 KB Output is correct
22 Correct 195 ms 10804 KB Output is correct
23 Correct 591 ms 10584 KB Output is correct
24 Correct 303 ms 10812 KB Output is correct
25 Correct 971 ms 10820 KB Output is correct
26 Correct 13 ms 10584 KB Output is correct
27 Correct 13 ms 10588 KB Output is correct
28 Correct 16 ms 10588 KB Output is correct
29 Correct 17 ms 10588 KB Output is correct
30 Correct 33 ms 10728 KB Output is correct
31 Correct 900 ms 10588 KB Output is correct
32 Correct 42 ms 10588 KB Output is correct
33 Correct 1008 ms 10828 KB Output is correct
34 Execution timed out 5057 ms 11308 KB Time limit exceeded
35 Halted 0 ms 0 KB -