oj.uz

Submission #906738

# Submission time Handle Problem Language Result Execution time Memory
906738 2024-01-14T23:33:17 Z typ_ik Synchronization (JOI13_synchronization) C++17
0 / 100
 8000 ms 262144 KB 
#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std; 

const int N = 3e5 + 128;
const int LOG = 20;
vector <int> g[N];
pair <int, int> edges[N];
int n, m, q;
int lift[N][LOG], depth[N], tin[N], tout[N];
int timer = 0;
int t[N], ans[N];

int sum(int r) {
    int ans = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1)
        ans += t[r];
    return ans;
} 

void add(int idx, int val) {
    for (; idx < n; idx = idx | (idx + 1))
        t[idx] += val;
} 

void dfs(int v, int p = 1) {
    if (v != 1)
        depth[v] = depth[p] + 1;

    lift[v][0] = p;
    for (int b = 1; b < LOG; b++)
        lift[v][b] = lift[lift[v][b-1]][b-1];

    tin[v] = timer++;
    for (auto& to : g[v])
        if (to != p)
            dfs(to, v);
    tout[v] = timer - 1;
}

int lca(int u, int v) {
    if (depth[v] > depth[u])
        swap(u, v);
    int k = depth[u] - depth[v];
    for (int b = 0; b < LOG; b++)
        if ((k >> b) & 1)
            u = lift[u][b];
    if (u == v)
        return u;
    for (int b = LOG - 1; b >= 0; b--)
        if (lift[v][b] != lift[u][b])
            v = lift[v][b], u = lift[u][b];
    return lift[u][0];
}

int get(int x) {
    return sum(tin[x]);
}

int get(int u, int v) {
    return get(u) + get(v) - 2 * get(lca(u, v));
}

int find_parent(int v) {
    for (int b = LOG - 1; b >= 0; b--)
        if (get(lift[v][b], v) == (1 << b))
            v = lift[v][b];
    return v;
}

int update(int v, int val) {
    add(tin[v], val);
    add(tout[v] + 1, -val);
} 

bool state[N];
int prev_time[N];

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        cin >> edges[i].first >> edges[i].second;
        g[edges[i].first].push_back(edges[i].second);
        g[edges[i].second].push_back(edges[i].first);
    }

    for (int i = 1; i <= n; i++)
        ans[i] = 1;

    dfs(1);

    for (int i = 0; i < m; i++) {
        int idx;
        cin >> idx;

        int u = edges[idx].first, v = edges[idx].second; 
        if (depth[u] > depth[v])
            swap(u, v); 
        
        if (state[idx]) {
            prev_time[idx] = ans[find_parent(u)];
            update(v, -1); 
            ans[find_parent(u)] = ans[find_parent(v)] = prev_time[idx]; 
        } else {
            int res = ans[find_parent(u)] + ans[find_parent(v)] - prev_time[idx];
            prev_time[idx] = 0;
            update(v, 1);
            ans[find_parent(u)] = res;
        }

        state[idx] = !state[idx]; 
    }  

    return;

    for (int i = 0; i < q; i++) {
        int x;
        cin >> x; 
        cout << ans[find_parent(x)] << '\n';
    }
}

main() { 
    boost;  
    solve();
    return 0;
}

Compilation message

synchronization.cpp: In function 'int update(int, int)':
synchronization.cpp:80:1: warning: no return statement in function returning non-void [-Wreturn-type]
   80 | }
      | ^
synchronization.cpp: At global scope:
synchronization.cpp:129:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  129 | main() {
      | ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 874 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8023 ms 32116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 509 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 659 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 515 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -