Submission #669692

#	Time	Username	Problem	Language	Result	Execution time	Memory
669692		dozer	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	233 ms	17844 KiB

cleaning

#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 (stderr)

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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30