제출 #1003691

#제출 시각아이디문제언어결과실행 시간메모리
1003691ErJSpring cleaning (CEOI20_cleaning)C++17
100 / 100
289 ms26240 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define vi vector<ll> #define vvi vector<vi> #define pp pair<ll, ll> #define rep(i,n) for(int i = 0; i < n; i++) vvi edges; vi val; vi parent, heavy, depth, head, pos; struct SegTree{ vi Itree, lazy; void init(int n){ while(n & (n - 1)) n++; Itree.resize(2*n, 0); lazy.resize(2*n, 0); } void update(int ind, int val){ ind += Itree.size() / 2; Itree[ind] = val; while(ind > 1){ ind /= 2; Itree[ind] = Itree[ind * 2] + Itree[2 * ind + 1]; } } void lazyEval(int u, int a, int b){ if(lazy[u] == 1){ Itree[u] = (b - a) - Itree[u]; if(2*u < lazy.size()){ lazy[2*u] ^= 1; lazy[2*u + 1] ^= 1; } lazy[u] = 0; } } ll get2(ll u, ll l, ll r, ll a, ll b){ lazyEval(u, a, b); if(l == a && r == b){ return Itree[u]; } ll s = (a + b)/2; if(r <= s){ return get2(2*u, l, r, a, s); }else if(l >= s){ return get2(2*u + 1, l, r, s, b); }else{ return get2(2*u, l, s, a, s) + get2(2*u + 1, s, r, s, b); } } ll get(ll l, ll r){ return get2(1, l, r, 0, Itree.size() / 2); } void XORange2(ll u, ll l, ll r, ll a, ll b){ lazyEval(u, a, b); if(l == a && r == b){ lazy[u] = 1; lazyEval(u, a, b); return; } ll s = (a + b)/2; if(r <= s){ XORange2(2*u, l, r, a, s); }else if(l >= s){ XORange2(2*u + 1, l, r, s, b); }else{ XORange2(2*u, l, s, a, s); XORange2(2*u + 1, s, r, s, b); } if(2*u < Itree.size()) { lazyEval(2*u, a, s); lazyEval(2*u + 1, s, b); Itree[u] = Itree[2*u] + Itree[2*u + 1]; } } void XORange(ll l, ll r){ XORange2(1, l, r, 0, Itree.size() / 2); } }; ll listy = 0; ll dfs(ll u){ ll max = -1; ll ind = -1; ll size = 1; ll aktVal = 0; rep(i, edges[u].size()){ ll v = edges[u][i]; if(parent[u] != v){ parent[v] = u; depth[v] = depth[u] + 1; ll x = dfs(v); aktVal += val[v]; size += x; if(x > max){ max = x; ind = v; } } } if(ind == -1){ val[u] = 1; listy++; }else{ val[u] = (aktVal % 2); } heavy[u] = ind; return size; } ll cur_pos; void decompose(int u, int h){ head[u] = h; pos[u] = cur_pos; cur_pos++; if(heavy[u] != -1){ decompose(heavy[u], h); } rep(i, edges[u].size()){ int v = edges[u][i]; if((parent[u] != v) && (v != heavy[u])){ decompose(v, v); } } } SegTree sg; void initSegTree(){ ll n = edges.size(); sg.init(n); rep(i, n){ sg.update(pos[i], val[i]); } } void initHLD(){ int n = edges.size(); parent.resize(n, -1); heavy.resize(n, -1); depth.resize(n, 0); pos.resize(n, -1); head.resize(n, -1); cur_pos = 0; dfs(0); decompose(0, 0); initSegTree(); } ll query(int u, int v){ ll ans = 0; for(; head[u] != head[v]; v = parent[head[v]]){ if(depth[head[u]] > depth[head[v]]){ swap(u, v); } ans = max(ans, sg.get(pos[head[v]], pos[v] + 1)); } ans = max(ans, sg.get(min(pos[v], pos[u]), max(pos[v], pos[u]) + 1)); return ans; } void queryUPD(int u, int v){ for(; head[u] != head[v]; v = parent[head[v]]){ if(depth[head[u]] > depth[head[v]]){ swap(u, v); } sg.XORange(pos[head[v]], pos[v] + 1); } sg.XORange(min(pos[v], pos[u]), max(pos[v], pos[u]) + 1); } int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); int n, q; cin >> n >> q; edges.resize(n); val.resize(n, 0); //rep(i, n) cin >> val[i]; rep(i, n-1){ int a, b; cin >> a >> b; a--; b--; edges[a].push_back(b); edges[b].push_back(a); } initHLD(); vi was(n, 0); if(edges[0].size() == 1) listy++; rep(i, q){ int d; cin >> d; vi add(d); vi upd; rep(j, d){ cin >> add[j]; add[j]--; if(!((edges[add[j]].size() == 1) && (was[add[j]] == 0))) { queryUPD(0, add[j]); upd.push_back(add[j]); } was[add[j]] = 1; } ll ans = sg.get(1, n); rep(j, upd.size()){ queryUPD(0, upd[j]); } rep(j, add.size()){ was[add[j]] = 0; } if((listy + upd.size()) % 2 == 0) cout << 2*(n - 1) - ans + d << endl; else cout << -1 << endl; } }

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

cleaning.cpp: In member function 'void SegTree::lazyEval(int, int, int)':
cleaning.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             if(2*u < lazy.size()){
      |                ~~~~^~~~~~~~~~~~~
cleaning.cpp: In member function 'void SegTree::XORange2(long long int, long long int, long long int, long long int, long long int)':
cleaning.cpp:81:16: 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]
   81 |         if(2*u < Itree.size()) {
      |            ~~~~^~~~~~~~~~~~~~
cleaning.cpp: In function 'long long int dfs(long long int)':
cleaning.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(i,n) for(int i = 0; i < n; i++)
......
  101 |     rep(i, edges[u].size()){
      |         ~~~~~~~~~~~~~~~~~~         
cleaning.cpp:101:5: note: in expansion of macro 'rep'
  101 |     rep(i, edges[u].size()){
      |     ^~~
cleaning.cpp: In function 'void decompose(int, int)':
cleaning.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(i,n) for(int i = 0; i < n; i++)
......
  134 |     rep(i, edges[u].size()){
      |         ~~~~~~~~~~~~~~~~~~         
cleaning.cpp:134:5: note: in expansion of macro 'rep'
  134 |     rep(i, edges[u].size()){
      |     ^~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(i,n) for(int i = 0; i < n; i++)
......
  225 |         rep(j, upd.size()){
      |             ~~~~~~~~~~~~~          
cleaning.cpp:225:9: note: in expansion of macro 'rep'
  225 |         rep(j, upd.size()){
      |         ^~~
cleaning.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(i,n) for(int i = 0; i < n; i++)
......
  228 |         rep(j, add.size()){
      |             ~~~~~~~~~~~~~          
cleaning.cpp:228:9: note: in expansion of macro 'rep'
  228 |         rep(j, add.size()){
      |         ^~~
#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...