oj.uz

Submission #669570

# Submission time Handle Problem Language Result Execution time Memory
669570 2022-12-06T18:46:30 Z dozer Spring cleaning (CEOI20_cleaning) C++14
9 / 100
 1000 ms 11388 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;
    dfs(maks.nd, node);
    nxt[maks.nd] = nxt[node];
    for (auto i : adj[node])
    {
        if (i != root && i != maks.nd)
        {
            nxt[i] = cntr;
            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)
{
    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 != 0)
    {
        int r = ind[node];
        int l = nxt[node];
        update(1, 1, n, l, r);
        node = par[nxt[node]];
    }
}

int32_t main()
{
    //fastio();
    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++)
    {
        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:141:9: warning: unused variable 'tot' [-Wunused-variable]
  141 |     int tot = dfs2(1, 0);//determine sz
      |         ^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 140 ms 4360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 3548 KB Output is correct
2 Correct 71 ms 3532 KB Output is correct
3 Correct 77 ms 10272 KB Output is correct
4 Correct 99 ms 9548 KB Output is correct
5 Correct 113 ms 11388 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 140 ms 4360 KB Output isn't correct
3 Halted 0 ms 0 KB -