제출 #660714

#제출 시각아이디문제언어결과실행 시간메모리
660714LoboSpring cleaning (CEOI20_cleaning)C++17
28 / 100
1093 ms11724 KiB
#include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; // #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() const int maxn = 1e5+10; int n, q, gr[maxn], p[maxn], sbl[maxn]; vector<int> g[maxn]; int cntl; int tr[4*maxn], lz[4*maxn], tin[maxn], tout[maxn], timer; int sbsz[maxn], phld[maxn]; void build(int no, int l, int r) { lz[no] = 0; if(l == r) { tr[no] = 0; return; } int lc=2*no,rc=2*no+1,mid=(l+r)>>1; build(lc,l,mid); build(rc,mid+1,r); tr[no] = tr[lc]+tr[rc]; } void flush(int no, int l, int r) { if(!lz[no]) return; tr[no] = (r-l+1)-tr[no]; if(l != r) { int lc=2*no,rc=2*no+1,mid=(l+r)>>1; lz[lc]^= 1; lz[rc]^= 1; } lz[no] = 0; } void upd(int no, int l, int r, int L, int R) { flush(no,l,r); if(l > R || r < L) return; if(l >= L && r <= R) { lz[no] = 1; flush(no,l,r); return; } int lc=2*no,rc=2*no+1,mid=(l+r)>>1; upd(lc,l,mid,L,R); upd(rc,mid+1,r,L,R); tr[no] = tr[lc]+tr[rc]; } int qry(int no, int l, int r, int L, int R) { flush(no,l,r); if(l > R || r < L) return 0; if(l >= L && r <= R) { return tr[no]; } int lc=2*no,rc=2*no+1,mid=(l+r)>>1; return qry(lc,l,mid,L,R)+qry(rc,mid+1,r,L,R); } void dfs(int u, int ant) { p[u] = ant; // tin[u] = ++timer; if(gr[u] == 1) { cntl++; sbl[u] = 1; } else sbl[u] = 0; sbsz[u] = 1; for(auto v : g[u]) if(v != ant) { dfs(v,u); sbl[u]^= sbl[v]; sbsz[u]+= sbsz[v]; } // tout[u] = timer; } void dfshld(int u, int ant) { tin[u] = ++timer; if(gr[u] == 1) { tout[u] = timer; return; } if(g[u][0] == ant) { swap(g[u][0],g[u][1]); } for(int i = 1; i < g[u].size(); i++) if(g[u][i] != ant) { if(sbsz[g[u][i]] > sbsz[g[u][0]]) swap(g[u][i],g[u][0]); } phld[g[u][0]] = phld[u]; dfshld(g[u][0],u); for(int i = 1; i < g[u].size(); i++) if(g[u][i] != ant) { int v = g[u][i]; phld[v] = v; dfshld(v,u); } tout[u] = timer; } void change(int v) { while(v != -1) { upd(1,1,n,tin[v],tin[v]); v = p[v]; } } void solve() { cin >> n >> q; for(int i = 1; i <= n-1; i++) { int u,v; cin >> u >> v; g[u].pb(v); g[v].pb(u); gr[u]++; gr[v]++; } int rt; for(int i = 1; i <= n; i++) { if(gr[i] != 1) { rt = i; break; } } dfs(rt,-1); dfshld(rt,-1); build(1,1,n); for(int i = 1; i <= n; i++) { if(sbl[i] == 1) upd(1,1,n,tin[i],tin[i]); } while(q--) { int D; cin >> D; vector<int> as; for(int i = 0; i < D; i++) { int v; cin >> v; as.pb(v); if(gr[v] == 1) { cntl--; change(v); } gr[v]++; cntl++; change(v); } if(cntl%2 == 1) { cout << -1 << endl; } else { int q1 = tr[1]+D; int q2 = n-1-tr[1]; cout << q1 + 2*q2 << endl; } for(int i = 0; i < D; i++) { int v = as[i]; gr[v]--; if(gr[v] == 1) { cntl++; change(v); } cntl--; change(v); } } } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("in.in", "r", stdin); // freopen("out.out", "w", stdout); int tt = 1; // cin >> tt; while(tt--) { solve(); } }

컴파일 시 표준 에러 (stderr) 메시지

cleaning.cpp: In function 'void flush(int, int, int)':
cleaning.cpp:39:31: warning: unused variable 'mid' [-Wunused-variable]
   39 |         int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
      |                               ^~~
cleaning.cpp: In function 'void dfshld(int, int)':
cleaning.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 1; i < g[u].size(); i++) if(g[u][i] != ant) {
      |                    ~~^~~~~~~~~~~~~
cleaning.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 1; i < g[u].size(); i++) if(g[u][i] != ant) {
      |                    ~~^~~~~~~~~~~~~
cleaning.cpp: In function 'void solve()':
cleaning.cpp:135:11: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |     dfshld(rt,-1);
      |     ~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...