# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1266277 | Bui_Quoc_Cuong | Making Friends on Joitter is Fun (JOI20_joitter2) | C++20 | 494 ms | 604 KiB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
int n, m;
namespace sub1 {
bitset <55> e[55];
void solve() {
int ans = 0;
while (m--) {
int u, v; cin >> u >> v;
if (e[u][v] == 0) {
ans++;
e[u][v] = 1;
}
while (1) {
bool add = 0;
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++) if (x != y && e[x][y]) {
for (int z = 1; z <= n; z++) if (z != x && z != y) {
if (e[y][z] && e[z][y] && e[x][z] == 0) {
e[x][z] = 1;
add = 1;
ans++;
}
}
}
}
if (add == 0) break;
}
cout << ans << "\n";
}
}
}
namespace sub2 {
vector <int> gout[2005], gin[2005];
bitset <2005> e[2005];
void solve() {
while (m--) {
int u, v; cin >> u >> v;
e[u][v] = 1;
int ans = 0;
gin[u].push_back(v);
gout[v].push_back(u);
queue <pair <int, int>> que;
que.push({u, v});
while (!que.empty()) {
int u = que.front().first, v = que.front().second;
que.pop();
if (e[u][v] && e[v][u]) {
for (int x = 1; x <= n; x++) if (x != u && x != v) {
if (e[x][v] && e[x][u] == 0) {
e[x][u] = 1;
que.push({x, u});
}
if (e[x][u] && e[x][v] == 0) {
e[x][v] = 1;
que.push({x, v});
}
}
}
}
for (int i = 1; i <= n; i++) ans+= e[i].count();
cout << ans << "\n";
}
}
}
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#define koa "kieuoanh"
if(fopen(koa".inp", "r")){
freopen(koa".inp", "r", stdin); freopen(koa".out", "w", stdout);
}
cin >> n >> m;
if (n <= 50) {
return sub1::solve(), 0;
}
if (n <= 2000) {
return sub2::solve(), 0;
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |