Submission #1266294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266294		icebear	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	686 ms	97620 KiB

joitter2

// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

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

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

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 1e5 + 5;
int numNode, numEdge;
set<int> G[N], rG[N], follower[N];
int lab[N];
queue<ii> mergeNode;
ll ans = 0;

void add_directed(int u, int v) {
    if (u == v) return;
    G[u].insert(v);
    rG[v].insert(u);

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

int root(int v) {
    return (lab[v] < 0 ? v : lab[v] = root(lab[v]));
}

int sz(int v) {
    v = root(v);
    return -lab[v] + (int)G[v].size() + (int)rG[v].size();
}

bool unite(int u, int v) {
    u = root(u); v = root(v);
    if (u == v) return false;
    if (sz(u) < sz(v)) swap(u, v);
    // x -> v and v <-> u -> x -> u
    ans += 1LL * -lab[u] * follower[v].size() + 1LL * -lab[v] * follower[u].size();

    for(int 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(int x : G[v]) add_directed(u, root(x));
    for(int x : rG[v]) add_directed(root(x), u);

    return true;
}

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

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

            add_directed(root(u), v);

            while(!mergeNode.empty()) {
                int u, v; tie(u, v) = mergeNode.front();
                mergeNode.pop();
                unite(u, v);
            }
        }
        cout << ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//     cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}

Compilation message (stderr)

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

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