oj.uz

Submission #198799

# Submission time Handle Problem Language Result Execution time Memory
198799 2020-01-27T17:56:15 Z osaaateiasavtnl Synchronization (JOI13_synchronization) C++14
30 / 100
 153 ms 38108 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 2e5 + 7;
vector <int> g[N];
ii ed[N];
set <ii> ms[N];
int l[N], num[N], par[N];
bool us[N];
int n, m, q;
void dfs(int u, int p) {
    par[u] = p;
    for (int v : g[u]) 
        if (v != p) 
            dfs(v, u);
}   
int ans = 0;
void solve(int u, int p, int x) {
    ++ans;
    for (int v : g[u]) 
        if (v != p) {
            auto t = ms[v].lower_bound(mp(x + 1, -1));
            if (t == ms[v].begin())
                continue;
            --t;
            solve(v, u, min(x, t->s));
        }   
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m >> q;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        ed[i] = mp(u, v);
        g[u].app(v); g[v].app(u);
    }   
    for (int i = 0; i < m; ++i) {
        cin >> num[i];
        --num[i];
    }
    int root;
    cin >> root;
    dfs(root, root);
    for (int i = 0; i < m; ++i) {
        int u = ed[num[i]].f, p = ed[num[i]].s;
        if (u == par[p])
            swap(u, p);
        if (us[num[i]]) {
            //cout << "insert " << u << " : " << l[num[i]] << ' ' << i << '\n';
            ms[u].insert(mp(l[num[i]], i));
        }
        else {
            l[num[i]] = i;
        }   
        us[num[i]] ^= 1;
    }   
    for (int i = 0; i < n - 1; ++i) {
        if (us[i]) {
            int u = ed[i].f, p = ed[i].s;
            if (u == par[p])
                swap(u, p);
            //cout << "insert " << u << " : " << l[i] << ' ' << m << '\n';
            ms[u].insert(mp(l[i], m));
        }   
    }   
    solve(root, root, N);
    cout << ans << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 16 ms 14456 KB Output is correct
6 Correct 15 ms 14584 KB Output is correct
7 Correct 25 ms 16248 KB Output is correct
8 Correct 23 ms 16248 KB Output is correct
9 Correct 22 ms 16252 KB Output is correct
10 Correct 153 ms 33144 KB Output is correct
11 Correct 147 ms 33144 KB Output is correct
12 Correct 118 ms 35192 KB Output is correct
13 Correct 105 ms 32876 KB Output is correct
14 Correct 132 ms 30200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 38108 KB Output is correct
2 Correct 93 ms 36084 KB Output is correct
3 Correct 82 ms 36856 KB Output is correct
4 Correct 75 ms 35704 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 37372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -