oj.uz

Submission #1064014

# Submission time Handle Problem Language Result Execution time Memory
1064014 2024-08-18T08:02:05 Z Boycl07 Synchronization (JOI13_synchronization) C++17
100 / 100
 222 ms 32548 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define int ll
#define rep(i, n) for(int i = 1; (i) <= (n); ++i)
#define forn(i, l, r) for(int i = (l); i <= (r); ++i)
#define ford(i, r, l) for(int i = (r); i >= (l); --i)
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "FFILL"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }


const int N = 1e5 + 3;
const int LIM = (1 << 16) + 3;
const int INF = 1e9 + 1;
const int LOG = 16;
int n, m, q;
vector<int> g[N];

int timedfs = 0;

pii e[N];

int up[N][LOG + 1], tin[N], tout[N], ans[N], b[N], bit[N];

bool c[N];


void update(int u, int v)
{
    for(; u <= n; u += u & -u) bit[u] += v;
}

int get(int u)
{
    int res = 0;
    for(; u; u -= u & -u) res += bit[u];
    return res;
}

void dfs(int u, int p)
{
    tin[u] = ++timedfs;
    up[u][0] = p;
    forn(i, 1, LOG) up[u][i] = up[up[u][i - 1]][i - 1];

    for(int v : g[u]) if(v != p) dfs(v, u);

    tout[u] = timedfs;
}

int root(int u)
{

    ford(i, LOG, 0) if(get(tin[u]) == get(tin[up[u][i]]))
        u = up[u][i];
    return u;
}

void solve()
{
    cin >> n >> m >> q;
    rep(i, n - 1)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        e[i] = {u, v};
    }

    dfs(1, 1);
    rep(i, n) update(tin[i], 1), update(tout[i] + 1, -1), ans[i] = 1;

    rep(_, m)
    {
        int idx;
        cin >> idx;
        int u = e[idx].fi, v = e[idx].se;

        if(up[u][0] == v) swap(u, v);

        if(c[v])
        {
            ans[v] = b[v] = ans[root(u)];
            update(tin[v], 1);
            update(tout[v] + 1, -1);
        }
        else
        {
            ans[root(u)] += ans[v] - b[v];
            update(tin[v], -1);
            update(tout[v] + 1, 1);
        }
        c[v] ^= 1;
    }
    rep(_, q)
    {
        int u;
        cin >> u;
        cout << ans[root(u)] << endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int TC = 1;

    if(fopen("note.inp", "r"))
    {
        freopen("note.inp", "r", stdin);
        freopen("note.out", "w", stdout);
    }


    while(TC--)
    {
        solve();
    }

    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2812 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 10 ms 5212 KB Output is correct
8 Correct 10 ms 5304 KB Output is correct
9 Correct 11 ms 5212 KB Output is correct
10 Correct 139 ms 27616 KB Output is correct
11 Correct 129 ms 27644 KB Output is correct
12 Correct 186 ms 31760 KB Output is correct
13 Correct 68 ms 27328 KB Output is correct
14 Correct 93 ms 26160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 28816 KB Output is correct
2 Correct 77 ms 28620 KB Output is correct
3 Correct 71 ms 30288 KB Output is correct
4 Correct 70 ms 30288 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 14 ms 5756 KB Output is correct
8 Correct 207 ms 32512 KB Output is correct
9 Correct 221 ms 32548 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 32500 KB Output is correct
2 Correct 113 ms 31316 KB Output is correct
3 Correct 108 ms 31576 KB Output is correct
4 Correct 107 ms 31616 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2812 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 14 ms 5368 KB Output is correct
7 Correct 171 ms 28500 KB Output is correct
8 Correct 222 ms 32508 KB Output is correct
9 Correct 102 ms 28608 KB Output is correct
10 Correct 112 ms 27472 KB Output is correct
11 Correct 90 ms 29976 KB Output is correct
12 Correct 103 ms 30080 KB Output is correct
13 Correct 108 ms 31572 KB Output is correct