oj.uz

Submission #464665

# Submission time Handle Problem Language Result Execution time Memory
464665 2021-08-13T15:54:53 Z Killer2501 Synchronization (JOI13_synchronization) C++14
100 / 100
 359 ms 37376 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "asd"
#define pll pair<ll, ll>
#define pii pair<pll, ll>
#define fi first
#define se second

using namespace std;
const ll mod = 1e9+7;
const ll N = 2e5+5;
const int base = 313;
ll n, m, t, k, T, ans, tong, a[N], b[N], c[N], h[N], P[N][20], in[N], out[N], d[N], fe[N];
vector<ll> adj[N];
vector<ll> kq;
bool ok[N];
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
void add(ll id, ll x)
{
    for(; id <= n; id += id & -id)fe[id] += x;
}
ll get(ll id)
{
    ll total = 0;
    for(; id; id -= id & -id)total += fe[id];
    return total;
}
void dfs(ll u, ll p)
{
    for(int i = 1; i < 20; i ++)P[u][i] = P[P[u][i-1]][i-1];
    in[u] = ++k;
    for(ll v : adj[u])
    {
        if(v == p)continue;
        P[v][0] = u;
        dfs(v, u);
    }
    out[u] = k;
}
ll findp(ll u)
{
    ll node = u;
    for(int i = 19; i >= 0; i --)
    {
        if(P[u][i] && get(in[P[u][i]]) == get(in[node]))u = P[u][i];
    }
    return u;
}
void sol()
{
    cin >> n >> m >> t;
    for(int i = 1; i < n; i ++)
    {
        cin >> a[i] >> b[i];
        adj[a[i]].pb(b[i]);
        adj[b[i]].pb(a[i]);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i ++)
    {
        add(in[i], 1);
        add(out[i]+1, -1);
        d[i] = 1;
    }
    while(m -- > 0)
    {
        ll i;
        cin >> i;
        ll u = a[i], v = b[i];
        if(P[u][0] == v)swap(u, v);
        if(ok[i])
        {
            d[v] = c[v] = d[findp(u)];
            add(in[v], 1);
            add(out[v]+1, -1);
        }
        else
        {
            d[findp(u)] += d[v] - c[v];
            add(in[v], -1);
            add(out[v]+1, 1);
        }
        //cout << d[findp(a[i])] <<" "<<d[findp(b[i])]<<'\n';
        ok[i] = !ok[i];
    }
    while(t -- > 0)
    {
        ll u;
        cin >> u;
        cout << d[findp(u)] << '\n';
    }
}
int main()
{
    if(fopen(task".INP", "r"))
    {
       freopen(task".INP", "r", stdin);
       freopen(task".OUT", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*
5 1
1 2
2 3
3 4
4 5
*/

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:107:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |        freopen(task".INP", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:108:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |        freopen(task".OUT", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 17 ms 7692 KB Output is correct
8 Correct 16 ms 7756 KB Output is correct
9 Correct 16 ms 7760 KB Output is correct
10 Correct 252 ms 32292 KB Output is correct
11 Correct 244 ms 32344 KB Output is correct
12 Correct 287 ms 36388 KB Output is correct
13 Correct 101 ms 32044 KB Output is correct
14 Correct 185 ms 31044 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 31392 KB Output is correct
2 Correct 107 ms 33148 KB Output is correct
3 Correct 143 ms 35056 KB Output is correct
4 Correct 140 ms 35100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 23 ms 8140 KB Output is correct
8 Correct 344 ms 37376 KB Output is correct
9 Correct 355 ms 37168 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 34344 KB Output is correct
2 Correct 211 ms 36036 KB Output is correct
3 Correct 220 ms 36396 KB Output is correct
4 Correct 208 ms 36172 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 21 ms 7816 KB Output is correct
7 Correct 309 ms 33160 KB Output is correct
8 Correct 348 ms 37132 KB Output is correct
9 Correct 149 ms 33136 KB Output is correct
10 Correct 193 ms 32216 KB Output is correct
11 Correct 145 ms 34604 KB Output is correct
12 Correct 150 ms 34684 KB Output is correct
13 Correct 214 ms 36256 KB Output is correct