oj.uz

Submission #669692

# Submission time Handle Problem Language Result Execution time Memory
669692 2022-12-07T05:36:33 Z dozer Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 233 ms 17844 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define L(node) node * 2
#define R(node) node * 2 + 1
 
int val[N], tree[4 * N], lazy[4 * N], ind[N], sz[N];
int arr[N], par[N], nxt[N], cnt[N];
int cntr = 1, n;
vector<int> adj[N];
 
void dfs(int node, int root)
{
    par[node] = root;
    ind[node] = cntr;
    cntr++;
    pii maks = {0, 0};
    for (auto i : adj[node])
    {
        if (i != root) maks = max(maks, {sz[i], i});
    }
    if (maks.nd == 0) return;
    nxt[maks.nd] = nxt[node];
    dfs(maks.nd, node);
    for (auto i : adj[node])
    {
        if (i != root && i != maks.nd)
        {
            nxt[i] = i;
            dfs(i, node);
        }
    }
}
 
int dfs2(int node, int root)
{
    sz[node] = 1;
    for (auto i : adj[node])
    {
        if (i != root) 
            sz[node] += dfs2(i, node);
    }
    return sz[node];
}
 
int dfs3(int node, int root)
{
    int flag = 0;
    for (auto i : adj[node])
        if (i != root) flag ^= dfs3(i, node);
    if (adj[node].size() == 1) flag ^= 1;
    val[node] += 1;
    if (flag == 0) val[node] ++;
    return flag;
}
 
void build (int node, int l, int r)
{
    if (l > r) return;
    if (l == r)
    {
        tree[node] = arr[l];
        return;
    }
    int mid = (l + r) / 2;
    build(L(node), l, mid);
    build(R(node), mid + 1, r);
    tree[node] = tree[L(node)] + tree[R(node)];
    
}
 
void push(int node, int l, int r)
{
    if (lazy[node] == 0) return;
    tree[node] = 3 * (r - l + 1) - tree[node];
    lazy[node] = 0;
    if (l == r) return;
    lazy[L(node)] ^= 1;
    lazy[R(node)] ^= 1;
}
 
 
void update(int node, int l, int r, int sl, int sr)
{
    push(node, l , r);
    if (l > r ||l > sr || r < sl) return;
    if (l >= sl && r <= sr)
    {
        lazy[node] ^= 1;
        push(node, l, r);
        return;
    }
    push(node, l, r);
    int mid = (l + r) / 2;
    update(L(node), l, mid, sl, sr);
    update(R(node), mid + 1, r, sl, sr);
    tree[node] = tree[L(node)] + tree[R(node)];
}
 
int find(int node, int l, int r, int sl, int sr)
{
	push(node, l, r);
    if (l > r || l > sr ||r < sl) return 0;
    if (l >= sl && r <= sr) return tree[node];
    int mid = (l + r) / 2;
    return find(L(node), l, mid, sl, sr) + find(R(node), mid + 1, r, sl, sr);
}
 
void all_the_way(int node)
{
    while(node > 1)
    {
        int r = ind[node];
        int l = ind[nxt[node]];
        update(1, 1, n, l, r);
        node = par[nxt[node]];
    }
}
 
int32_t main()
{
    fastio();
    //fileio();
    int q;
    cin>>n>>q;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    nxt[1] = 1;
    
    int tot = dfs2(1, 0);//determine sz
    dfs(1, 0);//init hld
    
    int flag = dfs3(1, 0);
    for (int i = 1; i <= n; i++)
    {
    	//cout<<i<<" : "<<nxt[i]<<endl;
        cnt[i] = adj[i].size();
        arr[ind[i]] = val[i];
    }
    
    build(1, 1, n);
    
    while(q--)
    {
        int d;
        cin>>d;
        int ans = d;
        vector<int> v;
        for (int i = 1; i <= d; i++)
        {
            int node;
            cin>>node;
            if (cnt[node] != 1) 
            {
                all_the_way(node);
                flag ^= 1;
            }
            cnt[node]++;
            v.pb(node);
            
        }
        ans += find(1, 1, n, 2, n);
        if (flag) cout<<-1<<endl;
        else cout<<ans<<endl;
        for (auto node : v)
        {
            cnt[node]--;
            if (cnt[node] != 1) 
            {
                flag ^= 1;
                all_the_way(node);
            }
        }
    }
 
    cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Compilation message

cleaning.cpp: In function 'int32_t main()':
cleaning.cpp:143:9: warning: unused variable 'tot' [-Wunused-variable]
  143 |     int tot = dfs2(1, 0);//determine sz
      |         ^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 119 ms 4400 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3500 KB Output is correct
2 Correct 39 ms 3540 KB Output is correct
3 Correct 27 ms 10264 KB Output is correct
4 Correct 53 ms 9744 KB Output is correct
5 Correct 54 ms 11476 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4048 KB Output is correct
2 Correct 46 ms 4088 KB Output is correct
3 Correct 52 ms 16760 KB Output is correct
4 Correct 113 ms 16244 KB Output is correct
5 Correct 44 ms 15196 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4972 KB Output is correct
2 Correct 41 ms 4812 KB Output is correct
3 Correct 10 ms 4608 KB Output is correct
4 Correct 11 ms 4744 KB Output is correct
5 Correct 12 ms 5148 KB Output is correct
6 Correct 55 ms 5204 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 7792 KB Output is correct
2 Correct 219 ms 7564 KB Output is correct
3 Correct 181 ms 6028 KB Output is correct
4 Correct 233 ms 9036 KB Output is correct
5 Correct 218 ms 8912 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 11084 KB Output is correct
2 Correct 120 ms 14680 KB Output is correct
3 Correct 185 ms 14764 KB Output is correct
4 Correct 165 ms 15564 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 119 ms 4400 KB Output is correct
3 Correct 37 ms 3500 KB Output is correct
4 Correct 39 ms 3540 KB Output is correct
5 Correct 27 ms 10264 KB Output is correct
6 Correct 53 ms 9744 KB Output is correct
7 Correct 54 ms 11476 KB Output is correct
8 Correct 46 ms 4048 KB Output is correct
9 Correct 46 ms 4088 KB Output is correct
10 Correct 52 ms 16760 KB Output is correct
11 Correct 113 ms 16244 KB Output is correct
12 Correct 44 ms 15196 KB Output is correct
13 Correct 69 ms 4972 KB Output is correct
14 Correct 41 ms 4812 KB Output is correct
15 Correct 10 ms 4608 KB Output is correct
16 Correct 11 ms 4744 KB Output is correct
17 Correct 12 ms 5148 KB Output is correct
18 Correct 55 ms 5204 KB Output is correct
19 Correct 158 ms 7792 KB Output is correct
20 Correct 219 ms 7564 KB Output is correct
21 Correct 181 ms 6028 KB Output is correct
22 Correct 233 ms 9036 KB Output is correct
23 Correct 218 ms 8912 KB Output is correct
24 Correct 215 ms 11084 KB Output is correct
25 Correct 120 ms 14680 KB Output is correct
26 Correct 185 ms 14764 KB Output is correct
27 Correct 165 ms 15564 KB Output is correct
28 Correct 163 ms 8524 KB Output is correct
29 Correct 169 ms 14368 KB Output is correct
30 Correct 56 ms 12740 KB Output is correct
31 Correct 111 ms 17844 KB Output is correct
32 Correct 232 ms 8812 KB Output is correct
33 Correct 143 ms 13032 KB Output is correct
34 Correct 152 ms 14872 KB Output is correct
35 Correct 146 ms 14788 KB Output is correct