Submission #1266371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266371		Bui_Quoc_Cuong	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	100 / 100	807 ms	111584 KiB

joitter2

#include <bits/stdc++.h>

template <class A, class B>
    bool maximize (A &a, const B b){
        if (a < b) {
            a = b;
            return true;
        } return false;
    }

template <class A, class B>
    bool minimize (A &a, const B b) {
        if (a > b) {
            a = b;
            return true;
        } return false;
    }

#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define fi first
#define se second
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define BIT(mask,i) ((mask>>(i))&1)
#define ll long long
using namespace std;

const int MAXN = 2e5 + 5;
const int oo = 2e9;
const long long INF = 1e18;
const int MOD = 1e9 + 7;

int numNode, numEdge;
int lab[MAXN];
set <int> follower[MAXN], gin[MAXN], gout[MAXN];
queue <pair <int, int>> QueueAdd;
long long ans = 0;

void init(void) {
    cin >> numNode >> numEdge;
    FOR(i, 1, numNode) {
        follower[i].insert(i);
        lab[i] = - 1;
    }
}

void addEdge (int u, int v) {
    if (u == v) return;

    gout[u].insert(v);
    gin[v].insert(u);

    if (gin[u].find(v) != gin[u].end()) {
        QueueAdd.push({u, v});
    }
}

int find (int x) {
    return lab[x] < 0 ? x : lab[x] = find(lab[x]);
}

int sz (int x) {
    x = find(x);
    return - lab[x] + gin[x].size() + gout[x].size();
}

void merge (int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    if (sz(u) < sz(v)) swap(u, v);

    ans+= 1LL * - lab[u] * follower[v].size() + 1LL * - lab[v] * follower[u].size();

    for (auto x : follower[v]) {
        if (follower[u].find(x) == follower[u].end()) follower[u].insert(x);
        else ans-= - lab[u] + - lab[v];
    }

    lab[u]+= lab[v];
    lab[v] = u;

    for (auto x : gin[v]) addEdge(find(x), u);
    for (auto x : gout[v]) addEdge(u, find(x));
}

void process(void) {
    while (numEdge--) {
        int u, v; cin >> u >> v;
        if (find(u) != find(v) && follower[find(v)].find(u) == follower[find(v)].end()) {
            v = find(v);
            ans+= - lab[v];
            follower[v].insert(u);

            addEdge(find(u), v);

            while (!QueueAdd.empty()) {
                auto [u, v] = QueueAdd.front();
                QueueAdd.pop();
                merge(u, v);
            }
        }
        cout << ans << "\n";
    }
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "joi20_jotter2"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    init();
    process();
    return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83