이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ar array
#define ld long double
const int N = 2e5 + 20;
const int INF = 1e15;
const int MOD = 1e9 + 7;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")
int s[4 * N];
int lz[4 * N];
int n;
void push(int k,int tl,int tr){
if(!lz[k])return;
s[k] = tr - tl + 1 - s[k];
if(tl != tr){
lz[k * 2] ^= lz[k];
lz[k * 2 + 1] ^= lz[k];
}
lz[k] = 0;
}
void upd(int k,int tl,int tr,int l,int r){
push(k, tl, tr);
if(l > tr || tl > r)return;
if(l <= tl && tr <= r){
lz[k] ^= 1;
push(k, tl, tr);
return;
}
int tm = (tl + tr) / 2;
upd(k *2, tl, tm, l , r);
upd(k * 2 + 1, tm + 1, tr,l, r);
s[k] = s[k * 2] + s[k * 2 + 1];
}
int get(){
push(1, 1, n);
return n - s[1];
}
vector<int> g[N];
int sz[N];
int dep[N];
int par[N];
int tin[N], tout[N];
void dfs1(int x,int p){
par[x] = p;
vector<int> v;
sz[x] = 1;
for(auto u: g[x]){
if(u == p)continue;
v.push_back(u);
dep[u] = dep[x] + 1;
dfs1(u, x);
sz[x] += sz[u];
}
g[x] = v;
for(int i = 1;i < g[x].size();i++){
if(sz[g[x][i]] > sz[g[x][0]])swap(g[x][i], g[x][0]);
}
}
int T;
int top[N];
void dfs2(int x, bool t){
tin[x] = ++T;
if(t)top[x] = top[par[x]];
else top[x] = x;
for(int i = 0;i < g[x].size();i++){
if(!i)dfs2(g[x][i], 1);
else dfs2(g[x][i], 0);
}
tout[x] = T;
}
void update(int u,int v){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]])swap(u, v);
upd(1, 1, n, tin[top[u]], tin[u]);
u = par[top[u]];
}
if(dep[u] > dep[v])swap(u, v);
upd(1, 1, n, tin[u], tin[v]);
}
bool A[N];
signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
int m;
cin>>n>>m;
int r;
for(int i = 1;i < n;i++){
int u, v;
cin>>u>>v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 0;i < n;i++){
if(g[i].size() >= 2){
r = i;
break;
}
}
dfs1(r, r);
dfs2(r, 0);
int cnt = 0;
for(int i = 0;i < n;i++){
if(g[i].empty())update(r, i), cnt++;
}
// assert(0);
while(m--){
int k;
cin>>k;
set<int> s;
for(int i = 0;i < k;i++){
int u;
cin>>u;
--u;
A[u] ^= 1;
s.insert(u);
}
int c = cnt;
for(auto u: s)c -= g[u].empty();
if((c + k) % 2){
for(auto u:s) A[u] = 0;
cout<<-1<<'\n';
continue;
}
for(auto u: s){
if((g[u].empty()) ^ A[u])update(r, u);
}
int q = get();
cout<< k + n + q - 2<<'\n';
for(auto u: s){
if((g[u].empty()) ^ A[u])update(r, u);
}
for(auto u: s)A[u] = 0;
}
}
컴파일 시 표준 에러 (stderr) 메시지
cleaning.cpp: In function 'void dfs1(long long int, long long int)':
cleaning.cpp:68:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 1;i < g[x].size();i++){
| ~~^~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs2(long long int, bool)':
cleaning.cpp:80:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = 0;i < g[x].size();i++){
| ~~^~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:144:35: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
144 | if((g[u].empty()) ^ A[u])update(r, u);
| ~~~~~~^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |