oj.uz

답안 #1003687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003687 2024-06-20T15:26:44 Z ErJ Spring cleaning (CEOI20_cleaning) C++17
26 / 100
 274 ms 26084 KB 
#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[upd[j]] = 1;
            }
        }
        ll ans = sg.get(1, n);
        rep(j, upd.size()){
            queryUPD(0, upd[j]);
            was[upd[j]] = 0;
        }
        if((listy + upd.size()) % 2 == 0) cout << 2*(n - 1) - ans + d << endl;
        else cout << -1 << endl;
    }
}

Compilation message

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()){
      |         ^~~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 11 ms 7772 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 3796 KB Output is correct
2 Correct 37 ms 3784 KB Output is correct
3 Correct 47 ms 25860 KB Output is correct
4 Correct 110 ms 26084 KB Output is correct
5 Correct 40 ms 23884 KB Output is correct

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 9820 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 11860 KB Output is correct
2 Runtime error 32 ms 21840 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 274 ms 18352 KB Output is correct
2 Correct 196 ms 22276 KB Output is correct
3 Correct 237 ms 20712 KB Output is correct
4 Correct 229 ms 22096 KB Output is correct

Subtask #7
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 11 ms 7772 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -