Submission #1296561

#TimeUsernameProblemLanguageResultExecution timeMemory
1296561musanna47Synchronization (JOI13_synchronization)C++20
100 / 100
188 ms21000 KiB
// Author: Muhtasim Hossain Musanna (Musanna47 / mhmusanna)

#include "bits/stdc++.h"

using namespace std;


#define nl "\n"
#define REPF(_i, _a, _b) for(int _i = _a; _i <= _b; _i++)
#define REPB(_i, _a, _b) for(int _i = _a; _i >= _b; _i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#define sza(_x) ((int)_x.size())
#define all(_x) _x.begin(), _x.end()
#define sort_des(_x) sort(all(_x), greater())
#define min_heap(_T, _pq, _cmp) auto _cmp = greater(); priority_queue<_T, vector<_T>, decltype(_cmp)> _pq(_cmp)


template<typename T1, typename T2>
using P = pair<T1, T2>;
template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using VVV = V<V<V<T>>>;
template<typename T>
using VVVV = V<V<V<V<T>>>>;


using S = string;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = P<int, int>;
using pll = P<ll, ll>;
using vi = V<int>;
using vvi = VV<int>;
using vll = V<ll>;
using vvll = VV<ll>;
using vpii = V<pii>;
using vpll = V<pll>;


template<typename T>
void pout(T a, string sep = " ", string fin = "\n") {
    cout << a.first << sep << a.second << fin;
}

template<typename T>
void print(T &a, ll l, ll r, string sep = " ", string fin = "\n") {
    for (ll i = l; i <= r; i++)
        cout << a[i] << sep;
    cout << fin;
}

template<typename T>
void printPairs(T &a, ll l, ll r, string fin = "\n") {
    for (ll i = l; i <= r; i++)
        pout(a[i]);
    cout << fin;
}

template<typename T>
void printAll(T &a, string sep = " ", string fin = "\n") {
    for (auto &ele: a)
        cout << ele << sep;
    cout << fin;
}

template<typename T>
void printPairsAll(T &a, string fin = "\n") {
    for (auto &ele: a)
        pout(ele);
    cout << fin;
}

template<typename... Args>
void read(Args &... args) {
    ((cin >> args), ...);
}

template<typename... Args>
void out(Args... args) {
    ((cout << args << " "), ...);
}

template<typename... Args>
void outln(Args... args) {
    ((cout << args << " "), ...);
    cout << nl;
}

template<typename T>
void vin(T &a, ll l, ll r) {
    for (ll i = l; i <= r; i++)
        cin >> a[i];
}

template<typename T>
void makeUnique(T &a) {
    a.erase(unique(all(a)), a.end());
}


using bll = __int128;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const double EPS = 1e-12;

mt19937_64 rnd(239);
//mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());


void prec() {

}

const int N = 1e5 + 5, D = 17;
int ans[N], tree[N<<1], uni[N], e1[N], e2[N], st[N], et[N], to[N][D], ct = 0;
vi G[N];
bool edge[N];

inline namespace BIT {
    int sz;

    void build(int n) {
        sz = n;
    }

    void pointAdd(int i, int x) {
        for (; i <= sz; tree[i] += x, i += (i & -i));
    }

    void rangeAdd(int l, int r, int x) {
        pointAdd(l, x);
        pointAdd(r + 1, -x);
    }

    int pointQuery(int i) {
        i = min(i, sz);
        int sum = 0;
        for (; i > 0; sum += tree[i], i -= (i & -i));
        return sum;
    }

    int rangeQuery(int l, int r) {
        return pointQuery(r) - pointQuery(l - 1);
    }
}


void dfs(int u = 1, int p = 1) {
    st[u] = ++ct;
    to[u][0] = p;
    for (auto &v: G[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
    et[u] = ++ct;
}

int get_root(int u) {
    REPB(d, D - 1, 0) {
        int x = to[u][d];
        if (u == x) break;
        if (!rangeQuery(st[x] + 1, st[u])) u = x;
    }
    return u;
}

void solve() {
    int n, m, q;
    read(n, m, q);
    REPF(i, 1, n - 1) {
        read(e1[i], e2[i]);
        G[e1[i]].emplace_back(e2[i]);
        G[e2[i]].emplace_back(e1[i]);
    }
    dfs();
    REPF(d, 1, D - 1) {
        REPF(i, 1, n) {
            to[i][d] = to[to[i][d - 1]][d - 1];
        }
    }
    fill(ans + 1, ans + n + 1, 1);
    fill(uni + 1, uni + n + 1, 1);
    build(n<<1);
    REPF(i, 2, n) {
        pointAdd(st[i], 1);
        pointAdd(et[i], -1);
    }
    REPF(i, 1, m) {
        int e;
        read(e);
        auto u = e1[e], v = e2[e];
        if (st[u] > st[v]) swap(u, v);
        u = get_root(u);
        edge[e] = !edge[e];
        if (edge[e]) {
            ans[u] += uni[v], uni[u] += uni[v], uni[v] = 0;
            pointAdd(st[v], -1);
            pointAdd(et[v], 1);
        } else {
            ans[v] = ans[u];
            pointAdd(st[v], 1);
            pointAdd(et[v], -1);
        }
    }
    REPF(i, 1, q) {
        int u;
        read(u);
        cout << ans[get_root(u)] << nl;
    }
}


void OJ() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

signed main() {
    // OJ();

    cin.tie(0)->sync_with_stdio(0);

    // cout << fixed << setprecision(10);

    // prec();

    int tc = 1;
    // cin >> tc;
    for (int i = 1; i <= tc; i++) {
        // cout << "Case " << i << ": ";
        solve();
    }

    return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'void OJ()':
synchronization.cpp:225:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:226:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...