Submission #895888

#	Time	Username	Problem	Language	Result	Execution time	Memory
895888		rukashii	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	5043 ms	47780 KiB

joitter2

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

#define file if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
// #define int long long
#define f first
#define s second

void setIn(string s) { freopen(s.c_str(), "r", stdin); }
void setOut(string s) { freopen(s.c_str(), "w", stdout); }
void setIO(string s = "") {
    if (s.size()) setIn(s+".inp"), setOut(s+".out");
}

const int maxn = 3e5 + 2;

long long ans, sz[maxn];
int n, m, a[maxn], b[maxn];
int lab[maxn];
set <int> adj[maxn], radj[maxn], child[maxn];
vector <pair <int, int>> to_join;

int Get(int u)
{
    return (lab[u] == -1) ? u : (lab[u] = Get(lab[u]));
}

void add_oneway_edge(int A, int B)
{
    adj[A].insert(B);
    radj[B].insert(A);

    if (radj[A].count(B))
    {
        to_join.push_back({Get(A), Get(B)});
    }
}

int get_size(int u)
{
    return child[u].size() + adj[u].size() + radj[u].size();
}

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

    // small to large, we merge v to u
    if (get_size(u) < get_size(v))
        swap(u, v);

    // we already got the edge from sz[u] -> v
    ans += sz[u] * child[v].size() + sz[v] * child[u].size();

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

    for (int p : child[v])
    {
        if (child[u].count(p))
        {
            ans -= sz[u];
        }
        else
            child[u].insert(p);
    }

    adj[u].erase(v); adj[v].erase(u);
    radj[u].erase(v); radj[v].erase(u);

    for (int p : radj[v])
    {
        adj[p].erase(v);
        add_oneway_edge(p, u);
    }
    for (int p : adj[v])
    {
        radj[p].erase(v);
        add_oneway_edge(u, p);
    }
}

signed main()
{
    // setIO();
    file;
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i] >> b[i];
    }

    for (int i = 1; i <= n; i++)
    {
        lab[i] = -1; sz[i] = 1;
        child[i].insert(i);
    }

    for (int i = 1; i <= m; i++)
    {
        int A = a[i], B = b[i];

        // A -> B
        if (Get(A) != Get(B) && !child[Get(B)].count(A))
        {
            child[Get(B)].insert(A);
            ans += sz[Get(B)];

            A = Get(A), B = Get(B);

            add_oneway_edge(A, B);
            while (to_join.size())
            {
                int X = to_join.back().f, Y = to_join.back().s;
                Merge(X, Y);
                to_join.pop_back();
            }
        }

        cout << ans << '\n';
    }
}   

Compilation message (stderr)

joitter2.cpp: In function 'void setIn(std::string)':
joitter2.cpp:9:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | void setIn(string s) { freopen(s.c_str(), "r", stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp: In function 'void setOut(std::string)':
joitter2.cpp:10:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void setOut(string s) { freopen(s.c_str(), "w", stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp: In function 'int main()':
joitter2.cpp:4:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:87:5: note: in expansion of macro 'file'
   87 |     file;
      |     ^~~~
joitter2.cpp:4:86: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:87:5: note: in expansion of macro 'file'
   87 |     file;
      |     ^~~~

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