oj.uz

Submission #691904

# Submission time Handle Problem Language Result Execution time Memory
691904 2023-02-01T00:29:24 Z NK_ Making Friends on Joitter is Fun (JOI20_joitter2) C++17
100 / 100
 2261 ms 245672 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())

using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, M; cin >> N >> M;

	vector<int> ID(N);
	vector<set<int>> G(N), F(N), FG(N), GF(N);

	ll ans = 0;

	int cur = 0;
	vector<array<int, 2>> MERGE; 

	auto merge = [&](int u, int v) {
		int gu = ID[u], gv = ID[v];
		if (gu == gv) return;

		ans -= (sz(F[gu]) - 1) * 1LL * sz(G[gu]);
		ans -= (sz(F[gv]) - 1) * 1LL * sz(G[gv]);

		// CHECK FOR OTHER MERGES;

		vector<int> add;

		if (sz(G[gu]) < sz(G[gv])) swap(gu, gv);
		for(const auto &x : G[gv]) {
			ID[x] = gu;
			G[gu].insert(x);
		}	

		for(const auto &x : F[gv]) F[gu].insert(x);
		
		for(const auto &x : GF[gv]) {
			if (GF[x].count(gu)) add.push_back(x);
			if (GF[x].count(gv)) add.push_back(x);
			GF[gu].insert(x); FG[x].insert(gu);
		}

		for(const auto &x : FG[gv]) {
			if (FG[x].count(gu)) add.push_back(x);
			if (FG[x].count(gv)) add.push_back(x);
			FG[gu].insert(x); GF[x].insert(gu);
		}

		int gx = ID[u];
		ans += (sz(F[gx]) - 1) * 1LL * sz(G[gx]);

		for(const auto &x : add) {
			if (x == gu || x == gv) continue;
			// cout << "ADDED: " << ID[x] << nl;
			MERGE.push_back({x, gx});
		}
	};

	for(int i = 0; i < N; i++) {
		ID[i] = i;
		G[i] = F[i] = {i};
	}

	for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; --u, --v; // u follows v
		int gu = ID[u], gv = ID[v];

		if (gu == gv) cout << ans << nl; // Already same group
		else if (F[gv].count(u)) cout << ans << nl; // Already fan of group
		else if (FG[gv].count(gu)) { // Merge groups + fans
			
			MERGE.push_back({gv, gu});
			while(cur < sz(MERGE)) {
				merge(MERGE[cur][0], MERGE[cur][1]); cur++;
			}

			cout << ans << nl;
		} else { 
			F[gv].insert(u);	
			FG[gu].insert(gv);
			GF[gv].insert(gu);

			ans += sz(G[gv]);
			cout << ans << nl;
		}
	}
	
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 320 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 324 KB Output is correct
27 Correct 1 ms 320 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 1 ms 316 KB Output is correct
33 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 320 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 324 KB Output is correct
27 Correct 1 ms 320 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 1 ms 316 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 3 ms 456 KB Output is correct
35 Correct 77 ms 4868 KB Output is correct
36 Correct 100 ms 7792 KB Output is correct
37 Correct 105 ms 7956 KB Output is correct
38 Correct 97 ms 7476 KB Output is correct
39 Correct 4 ms 1364 KB Output is correct
40 Correct 14 ms 3240 KB Output is correct
41 Correct 10 ms 3148 KB Output is correct
42 Correct 4 ms 1364 KB Output is correct
43 Correct 4 ms 1364 KB Output is correct
44 Correct 4 ms 1364 KB Output is correct
45 Correct 4 ms 1364 KB Output is correct
46 Correct 4 ms 1364 KB Output is correct
47 Correct 10 ms 2336 KB Output is correct
48 Correct 8 ms 2260 KB Output is correct
49 Correct 15 ms 3156 KB Output is correct
50 Correct 100 ms 8072 KB Output is correct
51 Correct 8 ms 1876 KB Output is correct
52 Correct 88 ms 6068 KB Output is correct
53 Correct 14 ms 2888 KB Output is correct
54 Correct 97 ms 6984 KB Output is correct
55 Correct 9 ms 2004 KB Output is correct
56 Correct 9 ms 2004 KB Output is correct
57 Correct 8 ms 2004 KB Output is correct
58 Correct 8 ms 2084 KB Output is correct
59 Correct 11 ms 3668 KB Output is correct
60 Correct 76 ms 6284 KB Output is correct
61 Correct 8 ms 2260 KB Output is correct
62 Correct 93 ms 7368 KB Output is correct

Subtask #3
83.0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 320 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 324 KB Output is correct
27 Correct 1 ms 320 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 1 ms 316 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 3 ms 456 KB Output is correct
35 Correct 77 ms 4868 KB Output is correct
36 Correct 100 ms 7792 KB Output is correct
37 Correct 105 ms 7956 KB Output is correct
38 Correct 97 ms 7476 KB Output is correct
39 Correct 4 ms 1364 KB Output is correct
40 Correct 14 ms 3240 KB Output is correct
41 Correct 10 ms 3148 KB Output is correct
42 Correct 4 ms 1364 KB Output is correct
43 Correct 4 ms 1364 KB Output is correct
44 Correct 4 ms 1364 KB Output is correct
45 Correct 4 ms 1364 KB Output is correct
46 Correct 4 ms 1364 KB Output is correct
47 Correct 10 ms 2336 KB Output is correct
48 Correct 8 ms 2260 KB Output is correct
49 Correct 15 ms 3156 KB Output is correct
50 Correct 100 ms 8072 KB Output is correct
51 Correct 8 ms 1876 KB Output is correct
52 Correct 88 ms 6068 KB Output is correct
53 Correct 14 ms 2888 KB Output is correct
54 Correct 97 ms 6984 KB Output is correct
55 Correct 9 ms 2004 KB Output is correct
56 Correct 9 ms 2004 KB Output is correct
57 Correct 8 ms 2004 KB Output is correct
58 Correct 8 ms 2084 KB Output is correct
59 Correct 11 ms 3668 KB Output is correct
60 Correct 76 ms 6284 KB Output is correct
61 Correct 8 ms 2260 KB Output is correct
62 Correct 93 ms 7368 KB Output is correct
63 Correct 502 ms 73432 KB Output is correct
64 Correct 489 ms 73428 KB Output is correct
65 Correct 492 ms 73368 KB Output is correct
66 Correct 348 ms 55480 KB Output is correct
67 Correct 1327 ms 194176 KB Output is correct
68 Correct 389 ms 55416 KB Output is correct
69 Correct 486 ms 53124 KB Output is correct
70 Correct 375 ms 55448 KB Output is correct
71 Correct 346 ms 55464 KB Output is correct
72 Correct 1006 ms 105196 KB Output is correct
73 Correct 1083 ms 113324 KB Output is correct
74 Correct 2261 ms 154644 KB Output is correct
75 Correct 741 ms 64492 KB Output is correct
76 Correct 1376 ms 103592 KB Output is correct
77 Correct 1352 ms 104156 KB Output is correct
78 Correct 345 ms 61972 KB Output is correct
79 Correct 640 ms 71696 KB Output is correct
80 Correct 357 ms 60500 KB Output is correct
81 Correct 562 ms 66872 KB Output is correct
82 Correct 1233 ms 89116 KB Output is correct
83 Correct 1203 ms 89116 KB Output is correct
84 Correct 924 ms 89184 KB Output is correct
85 Correct 961 ms 89064 KB Output is correct
86 Correct 1278 ms 245464 KB Output is correct
87 Correct 1369 ms 245672 KB Output is correct
88 Correct 1138 ms 109692 KB Output is correct
89 Correct 1294 ms 100012 KB Output is correct