oj.uz

답안 #756963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756963 2023-06-12T11:49:22 Z Sam_a17 Spring cleaning (CEOI20_cleaning) C++17
54 / 100
 554 ms 37624 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include <atcoder/all>
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
 
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
#define ll long long
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
void print(long double t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T> void print(T v[],T n) {cerr << "["; for(int i = 0; i < n; i++) {cerr << v[i] << " ";} cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for random generations
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 myrand(131);
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
long long ka() {
	long long x = 0;
	bool z = false;
	while (1)
	{
		char y = getchar();
		if (y == '-')
			z = true;
		else if ('0' <= y && y <= '9')
			x = x * 10 + y - '0';
		else
		{
			if (z)
				x *= -1;
			return x;
		}
	}
}
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  // if (str != "") {
  //   freopen((str + ".in").c_str(), "r", stdin);
  //   freopen((str + ".out").c_str(), "w", stdout);
  // }else {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
  // }
}
 
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 4e5 + 10, M = 7e6 + 10;
vector<int> adj[N];
int n, q, deg[N];

int dp[N][3];
int add[N], depth[N];
int two[N];
bool is_leaf[N];

int sz[N], id[N], tp[N], p[N], dep[N];
struct node {
  long long ones, twos, lazy;
};

node combine(node a, node b) {
  a.ones += b.ones;
  a.twos += b.twos;
  a.lazy = 0;
  return a;
}

struct segTree {

  vector<node> tree;
  int size = 1;
 

  void propagate(int x, int lx, int rx) {
    if(rx - lx == 1 || tree[x].lazy % 2 == 0) {
      tree[x].lazy = 0;
      return;
    }
 
    int mid = (lx + rx) / 2;
 
    tree[2 * x + 1].lazy += tree[x].lazy;
    swap(tree[2 * x + 1].ones, tree[2 * x + 1].twos);
 
    tree[2 * x + 2].lazy += tree[x].lazy;
    swap(tree[2 * x + 2].ones, tree[2 * x + 2].twos);
 
    tree[x].lazy = 0;
  }
 
  void init(long long s) {
    while(size < s) {
      size *= 2;
    }
    tree.assign(2 * size - 1, {0, 0, 0});
  }
 
  void upd(int l, int r, long long value, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if(lx >= r || rx <= l) {
      return;
    }
 
    if(lx >= l && rx <= r) {
      if(value % 2 == 1) {
        swap(tree[x].ones, tree[x].twos);
      }
      tree[x].lazy += value;
      propagate(x, lx, rx);
      return;
    }
 
    int mid = (lx + rx) / 2;
    upd(l, r, value, 2 * x + 1, lx, mid);
    upd(l, r, value, 2 * x + 2, mid, rx);
    tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
  }
 
  void upd(int l, int r, long long value) {
    upd(l, r, value, 0, 0, size);
  }

  void upd2(int l, int r, long long value, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if(lx >= r || rx <= l) {
      return;
    }
 
    if(lx >= l && rx <= r) {
      if(value == 1) {
        tree[x].ones = 1;
      } else {
        tree[x].twos = 1;
      }
      propagate(x, lx, rx);
      return;
    }
 
    int mid = (lx + rx) / 2;
    upd2(l, r, value, 2 * x + 1, lx, mid);
    upd2(l, r, value, 2 * x + 2, mid, rx);
    tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
  }
 
  void upd2(int l, int r, long long value) {
    upd2(l, r, value, 0, 0, size);
  }
 
  node qry(int l, int r, int x, int lx, int rx) {
    propagate(x, lx, rx);
    if(lx >= r || rx <= l) {
      return {0, 0, 0};
    }
 
    if(lx >= l && rx <= r) {
      return tree[x];
    }
 
    int mid = (lx + rx) / 2;
    node s1 = qry(l, r, 2 * x + 1, lx, mid);
    node s2 = qry(l, r, 2 * x + 2, mid, rx);
    return combine(s1, s2);
  }
 
  node qry(int l, int r) {
    return qry(l, r, 0, 0, size);
  }
};
segTree seg;

int dfs_sz(int cur, int par) {
	sz[cur] = 1;
	p[cur] = par;
	for (int chi : adj[cur]) {
		if (chi == par) continue;
		dep[chi] = dep[cur] + 1;
		p[chi] = cur;
		sz[cur] += dfs_sz(chi, cur);
	}
	return sz[cur];
}

int ct = 1;

void dfs_hld(int cur, int par, int top) {
	id[cur] = ct++;
	tp[cur] = top;

  if(dp[cur][2] != -1) {
    seg.upd2(id[cur], id[cur] + 1, 2);
  } else {
    seg.upd2(id[cur], id[cur] + 1, 1);
  }


	int h_chi = -1, h_sz = -1;
	for (int chi : adj[cur]) {
		if (chi == par) continue;
		if (sz[chi] > h_sz) {
			h_sz = sz[chi];
			h_chi = chi;
		}
	}
	if (h_chi == -1) return;
	dfs_hld(h_chi, cur, top);
	for (int chi : adj[cur]) {
		if (chi == par || chi == h_chi) continue;
		dfs_hld(chi, cur, chi);
	}
}

node path(int a, int b) {
  node answ = {0, 0, 0};
  while(tp[a] != tp[b]) {
    node curr = seg.qry(id[tp[a]], id[a] + 1);
    answ = combine(answ, curr);
    a = p[tp[a]];
  }
 
  //
  node curr = seg.qry(id[b], id[a] + 1);
  answ = combine(answ, curr);
  return answ;
}

void change_path(int a, int b) {
  while(tp[a] != tp[b]) {
    seg.upd(id[tp[a]], id[a] + 1, 1);
    a = p[tp[a]];
  }
  //
  seg.upd(id[b], id[a] + 1, 1);
}


void dfs(int node, int parent) {
  dp[node][1] = dp[node][2] = -1;

  int cnt = 0;
  for(auto i: adj[node]) {
    if(i == parent) continue;
    cnt++;
    dfs(i, node);
  }

  cnt += add[node];

  if(!cnt) {
    dp[node][1] = 0;
    is_leaf[node] = 1;
  } else {
    long long s = 0, c = 0;
    for(auto i: adj[node]) {
      if(i == parent) continue;

      if(dp[i][1] != -1) {
        c += 1;
        s += dp[i][1] + 1;
      } else if(dp[i][2] != -1) {
        c += 2;
        s += dp[i][2] + 2;
      }
    }

    s += add[node];
    c += add[node];

    if(c & 1) {
      dp[node][1] = s;
    } else {
      dp[node][2] = s;
    }
  }

  add[node] = 0;
}

void dfs2(int node, int parent) {
  if(parent) {
    two[node] += two[parent];
    depth[node] = depth[parent] + 1;
    if(dp[node][2] != -1) {
      two[node]++;
    }  
  }
  
  for(auto i: adj[node]) {
    if(i == parent) continue;
    dfs2(i, node);
  }
}

int slv(int start, int a) {
  int ans = dp[start][1];
  for(int i = 1; i <= 1; i++) {

    if(is_leaf[a]) {
      
      if(dp[start][2] == -1) {
        ans = -1;
      } else {
        ans = dp[start][2] + 1;
      }

      break;
    } else if(ans == -1) {
      break;
    }

    ans += 1;
    ans -= two[a];
    ans += depth[a] - two[a];
  }

  return ans;
}

void solve_() {
  cin >> n >> q;
  // n = ka(), q = ka();

  for(int i = 1; i <= n - 1; i++) {
    int a, b; 
    // a = ka(), b = ka();
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);

    deg[a]++, deg[b]++;
  }

  int start = -1;
  for(int i = 1; i <= n; i++) {
    if(deg[i] > 1) {
      start = i;
      break;
    }
  }

  seg.init(2 * n + 10);
  dfs(start, 0);
  dfs2(start, 0);
  dfs_sz(start, 0);
  dfs_hld(start, 0, 1);

  while(q--) {
    int d;
    cin >> d;

    long long cur = 0, ans = 0;
    int cr = 0;
    if(dp[start][1] != -1) {
      ans = dp[start][1];
      cur = 1;
    } else {
      ans = dp[start][2];
      cur = 2;
    }

    vector<int> vec;
    vector<pair<int, int>> don;
    int ok = 0;
    for(int i = 1; i <= d; i++) {
      int a; cin >> a, cr = a;
      vec.push_back(a);
      deg[a]++;

      if(a == start) {
        ans += 1;
        change_path(a, start);
        don.push_back({a, start});
        cur++;
        ok = 1;
        continue;
      } else if(deg[a] == 2) {
        ans += 1;
        ok = 1;
        continue;
      }

      cur++;

      auto u = path(a, start);
      auto uu = path(start, start);
      assert(uu.ones <= 1);
      assert(uu.twos <= 1);

      u.ones -= uu.ones;
      u.twos -= uu.twos;

      // assert(u.twos == two[a]);
      assert(u.ones == (depth[a] - u.twos));
      // u.ones = depth[a] - u.twos;

      ans += 1;
      ans -= u.twos;
      ans += u.ones;

      change_path(a, start);
      don.push_back({a, start});
    }

    if(cur % 2 == 1) { 
      cout << -1 << '\n';
    } else {
      cout << ans << '\n';
    }

    for(auto i: vec) {
      deg[i]--;
    }

    for(auto i: don) {
      change_path(i.first, i.second);
    }
  }
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1; 
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

cleaning.cpp: In member function 'void segTree::propagate(int, int, int)':
cleaning.cpp:131:9: warning: unused variable 'mid' [-Wunused-variable]
  131 |     int mid = (lx + rx) / 2;
      |         ^~~
cleaning.cpp: In function 'void solve_()':
cleaning.cpp:402:9: warning: variable 'cr' set but not used [-Wunused-but-set-variable]
  402 |     int cr = 0;
      |         ^~
cleaning.cpp:413:9: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  413 |     int ok = 0;
      |         ^~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 229 ms 14564 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 11912 KB Output is correct
2 Correct 135 ms 11840 KB Output is correct
3 Correct 79 ms 30384 KB Output is correct
4 Correct 162 ms 29268 KB Output is correct
5 Correct 187 ms 31452 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 12756 KB Output is correct
2 Correct 146 ms 12760 KB Output is correct
3 Correct 120 ms 37624 KB Output is correct
4 Correct 316 ms 37616 KB Output is correct
5 Correct 106 ms 36120 KB Output is correct

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 15200 KB Output is correct
2 Correct 82 ms 14496 KB Output is correct
3 Correct 24 ms 14420 KB Output is correct
4 Correct 24 ms 15060 KB Output is correct
5 Correct 28 ms 15188 KB Output is correct
6 Runtime error 112 ms 30204 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 309 ms 27564 KB Output is correct
2 Correct 554 ms 27376 KB Output is correct
3 Correct 388 ms 18740 KB Output is correct
4 Correct 527 ms 27476 KB Output is correct
5 Correct 536 ms 27364 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 30612 KB Output is correct
2 Correct 293 ms 33212 KB Output is correct
3 Correct 366 ms 33316 KB Output is correct
4 Correct 391 ms 32836 KB Output is correct

Subtask #7
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 229 ms 14564 KB Output is correct
3 Correct 132 ms 11912 KB Output is correct
4 Correct 135 ms 11840 KB Output is correct
5 Correct 79 ms 30384 KB Output is correct
6 Correct 162 ms 29268 KB Output is correct
7 Correct 187 ms 31452 KB Output is correct
8 Correct 147 ms 12756 KB Output is correct
9 Correct 146 ms 12760 KB Output is correct
10 Correct 120 ms 37624 KB Output is correct
11 Correct 316 ms 37616 KB Output is correct
12 Correct 106 ms 36120 KB Output is correct
13 Correct 195 ms 15200 KB Output is correct
14 Correct 82 ms 14496 KB Output is correct
15 Correct 24 ms 14420 KB Output is correct
16 Correct 24 ms 15060 KB Output is correct
17 Correct 28 ms 15188 KB Output is correct
18 Runtime error 112 ms 30204 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -