Submission #1261713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261713		4o2a	Synchronization (JOI13_synchronization)	C++20	100 / 100	183 ms	37408 KiB

synchronization

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define _F "what"
using namespace std;
typedef long long ll;

constexpr int N = 1e5 + 1, M = 2e5 + 1;
int n, m, q;
vector<int> par(N, -1), sz(N, 1), lab(N, 1), pre(N), st[4*M], Q, L(N);
pair<int, int> E[N];
stack<pair<int, int>> rb;

int find_set(int u)
{
    return (par[u] == -1 ? u : find_set(par[u]));
}

void merge_set(int i)
{
    int u = find_set(E[i].fi), v = find_set(E[i].se);
    if (u == v)
    {
        rb.push({-1, -1});
        return;
    }
    else
    {
        if (sz[u] < sz[v])
            swap(u, v);
        int new_lab = lab[u] + lab[v] - pre[i];
        lab[u] = new_lab;
        par[v] = u;
        sz[u] += sz[v];
        rb.push({v, i});
    }
}

void rollback()
{
    auto p = rb.top(); rb.pop();
    int v = p.fi, i = p.se;
    if (v == -1)
        return;
    int u = par[v];
    lab[v] = pre[i] = lab[u];
    par[v] = -1;
    sz[u] -= sz[v];
}

void add(int i, int l, int r, int tl = 1, int tr = m, int v = 1)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
        st[v].pb(i);
    else
    {
        int tm = (tl+tr)/2;
        add(i, l, min(tm, r), tl, tm, 2*v);
        add(i, max(l, tm+1), r, tm+1, tr, 2*v+1);
    }
}

void dfs_st(int tl = 1, int tr = m, int v = 1)
{
    for (int i: st[v])
        merge_set(i);
    if (tl == tr && tl == m)
        for (int u: Q)
            cout<<lab[find_set(u)]<<"\n";
    else if (tl != tr)
    {
        int tm = (tl+tr)/2;
        dfs_st(tl, tm, 2*v);
        dfs_st(tm+1, tr, 2*v+1);
    }
    for (int i = 0; i < st[v].size(); ++i)
        rollback();
}

void solve()
{
    cin>>n>>m>>q;
    Q.resize(q);
    for (int i = 1; i < n; ++i)
        cin>>E[i].fi>>E[i].se;
    for (int i = 1; i <= m; ++i)
    {
        int x; cin>>x;
        if (L[x] > 0)
        {
            add(x, L[x], i-1);
            L[x] = 0;
        }
        else
            L[x] = i;
    }
    for (int i = 1; i < n; ++i)
        if (L[i] > 0)
            add(i, L[i], m);
    for (int i = 0; i < q; ++i)
        cin>>Q[i];
    dfs_st();
}

int main()
{
    if (fopen(_F".INP", "r"))
    {
        freopen(_F".INP", "r", stdin);
        freopen(_F".OUT", "w", stdout);
    }
    else if (fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        //freopen("test.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int Test = 1; //cin>>Test;
    while (Test--) solve();
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.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(_F".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(_F".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40