oj.uz

Submission #1097739

# Submission time Handle Problem Language Result Execution time Memory
1097739 2024-10-08T05:31:11 Z Neco_arc Synchronization (JOI13_synchronization) C++17
100 / 100
 145 ms 20208 KB 
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Synchronization"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, m, q;
int cl[maxn], ans[maxn], last[maxn];
int p[maxn], In[maxn], Out[maxn];
pair<int, int> E[maxn];
vector<int> edges[maxn];

void pre_dfs(int u, int par) {
    static int Time = 0;
    In[u] = ++Time, p[Time] = u;
    for(int v : edges[u]) if(v != par) {
        pre_dfs(v, u);
    }
    Out[u] = Time;
}

struct IT {
    int st[4 * maxn];

    void update(int x, int val, int id = 1, int l = 1, int r = n) {
        if(l > x || r < x) return;
        if(l == r) return st[id] = val, void();

        int mid = (l + r) >> 1;
        update(x, val, _left), update(x, val, _right);
        st[id] = max(st[id * 2], st[id * 2 + 1]);
    }

    int get(int x, int val, int id = 1, int l = 1, int r = n) {
        if(l > x || st[id] < val) return -1;
        if(l == r) return p[l];

        int mid = (l + r) >> 1;
        int w = get(x, val, _right);
        if(w == -1) w = get(x, val, _left);

        return w;
    }

} St;

void solve()
{
    cin >> n >> m >> q;
    fi(i, 1, n - 1) {
        int x, y; cin >> x >> y;
        E[i] = {x, y};
        edges[x].push_back(y), edges[y].push_back(x);
    }

    pre_dfs(1, 0);
    fi(i, 1, n) {
        St.update(In[i], Out[i]);
        ans[i] = 1;
    }

    fi(i, 1, m) {
        int id, u, v; cin >> id;
        tie(u, v) = E[id]; if(In[u] > In[v]) swap(u, v);
        int p = St.get(In[u], Out[u]);

        if(!cl[id]) {
            ans[p] += ans[v] - last[v];
            St.update(In[v], 0);
        }
        else {
            last[v] = ans[v] = ans[p];
            St.update(In[v], Out[v]);
        }

        cl[id] ^= 1;
    }

    fi(i, 1, q) {
        int x; cin >> x;
        cout << ans[St.get(In[x], Out[x])] << '\n';
    }


}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    int nTest = 1;
//    cin >> nTest;

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


    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 5112 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5176 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 10 ms 5980 KB Output is correct
8 Correct 10 ms 5980 KB Output is correct
9 Correct 10 ms 5980 KB Output is correct
10 Correct 105 ms 14792 KB Output is correct
11 Correct 106 ms 14812 KB Output is correct
12 Correct 106 ms 19444 KB Output is correct
13 Correct 79 ms 14780 KB Output is correct
14 Correct 72 ms 13808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 14676 KB Output is correct
2 Correct 60 ms 16576 KB Output is correct
3 Correct 54 ms 18480 KB Output is correct
4 Correct 54 ms 18484 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 5176 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5168 KB Output is correct
5 Correct 3 ms 5052 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 11 ms 6492 KB Output is correct
8 Correct 145 ms 20052 KB Output is correct
9 Correct 112 ms 20208 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 17232 KB Output is correct
2 Correct 72 ms 19540 KB Output is correct
3 Correct 72 ms 19544 KB Output is correct
4 Correct 70 ms 19688 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 13 ms 6204 KB Output is correct
7 Correct 133 ms 15700 KB Output is correct
8 Correct 116 ms 20052 KB Output is correct
9 Correct 95 ms 15788 KB Output is correct
10 Correct 96 ms 15184 KB Output is correct
11 Correct 92 ms 17796 KB Output is correct
12 Correct 83 ms 17820 KB Output is correct
13 Correct 90 ms 19536 KB Output is correct