oj.uz

Submission #357818

# Submission time Handle Problem Language Result Execution time Memory
357818 2021-01-24T17:53:24 Z parsabahrami Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 10 ms 14828 KB 
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e5 + 10;
int S[N], rt[N], n, m; ll ret; set<int> in[N], out[N], comp[N];
queue<pii> Q;

int Find(int v) {
    return !rt[v] ? v : rt[v] = Find(rt[v]);
}

inline void add_edge(int u, int v) {
    out[u].insert(v), in[v].insert(u);
    if (out[v].count(u)) Q.push({u, v});
}

void Union(int u, int v) {
    u = Find(u), v = Find(v);
    if  (u == v) return;
    if (SZ(comp[u]) + SZ(in[u]) + SZ(out[u]) > SZ(comp[v]) + SZ(in[v]) + SZ(out[v])) swap(u, v);
    ret += 1ll * S[u] * SZ(comp[v]) + 1ll * S[v] * SZ(comp[u]);
    rt[u] = v;
    S[v] += S[u];
    for (int w : comp[u]) {
        if (comp[v].count(w)) ret -= S[v];
        else comp[v].insert(w);
    } 
    in[u].erase(v), out[u].erase(v), in[v].erase(u), out[v].erase(u);
    for (int w : in[u]) {
        out[w].erase(u);
        add_edge(w, v);
    } 
    for (int w : out[u]) {
        in[w].erase(u);
        add_edge(v, w);
    }
}

int main() {
    fill(S, S + N, 1);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) comp[i].insert(i);
    for (; m; m--) {
        int u, v; scanf("%d%d", &u, &v);
        v = Find(v);
        if (Find(u) != v && !in[v].count(Find(u))) {
            comp[v].insert(u);
            ret += S[v];
            add_edge(Find(u), v);
            while (SZ(Q)) {
                int U = Q.front().F, V = Q.front().S; Q.pop();
                Union(U, V);
            }
        }
        printf("%lld\n", ret);
    }
    return 0;
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
joitter2.cpp:53:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14828 KB Output is correct
2 Correct 10 ms 14828 KB Output is correct
3 Correct 10 ms 14828 KB Output is correct
4 Correct 10 ms 14828 KB Output is correct
5 Incorrect 10 ms 14828 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14828 KB Output is correct
2 Correct 10 ms 14828 KB Output is correct
3 Correct 10 ms 14828 KB Output is correct
4 Correct 10 ms 14828 KB Output is correct
5 Incorrect 10 ms 14828 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14828 KB Output is correct
2 Correct 10 ms 14828 KB Output is correct
3 Correct 10 ms 14828 KB Output is correct
4 Correct 10 ms 14828 KB Output is correct
5 Incorrect 10 ms 14828 KB Output isn't correct
6 Halted 0 ms 0 KB -