oj.uz

답안 #603593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603593 2022-07-24T08:36:58 Z 반딧불(#8427) 동기화 (JOI13_synchronization) C++17
0 / 100
 875 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Pair{
    int min, max;
    Pair(){}
    Pair(int min, int max): min(min), max(max){}

    Pair operator+(const Pair &r)const{
        return Pair(::min(min, r.min), ::max(max, r.max));
    }
};

struct segTree{
    Pair tree[800002];
    int lazy[800002];
    vector<vector<pair<int*, int> > > history;

    void init(int i, int l, int r){
        lazy[i] = -1;
        if(l==r){
            tree[i].min = tree[i].max = l;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void save(){
        history.push_back(vector<pair<int*, int> >());
    }

    void record(int &x){
        history.back().push_back(make_pair(&x, x));
    }

    void record(Pair &x){
        record(x.min), record(x.max);
    }

    void rollback(){
        for(int i=(int)history.back().size()-1; i>=0; i--){
            *(history.back()[i].first) = history.back()[i].second;
        }
        history.pop_back();
    }

    void propagate(int i, int l, int r){
        if(lazy[i] == -1) return;
        record(tree[i]);
        tree[i] = Pair(lazy[i], lazy[i]);
        if(l!=r){
            record(lazy[i*2]);
            record(lazy[i*2+1]);
            lazy[i*2] = lazy[i*2+1] = lazy[i];
        }
        lazy[i] = -1;
    }

    void update(int i, int l, int r, int s, int e, int v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            record(lazy[i]);
            lazy[i] = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        record(tree[i]);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    Pair query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return Pair(1e9, 0);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
    }

    int lower_bound(int i, int l, int r, int x){
        propagate(i, l, r);
        if(tree[i].max < x) return r+1;
        if(l==r) return l;
        int m = (l+r)>>1;
        propagate(i*2, l, m);
        if(tree[i*2].max >= x) return lower_bound(i*2, l, m, x);
        else return lower_bound(i*2+1, m+1, r, x);
    }
};

struct Edge{
    int x, y, idx;
    Edge(){}
    Edge(int x, int y, int idx): x(x), y(y), idx(idx){}
};

int n, m, q;
int ex[100002], ey[100002];
vector<Edge> link[100002];
int arr[200002];
int query[100002];
vector<int> toggle[100002];
int ans[100002];

int root;
bool centroidUsed[100002];
int subTreeSize[100002];

segTree tree;
int tn;
vector<int> timeList;
vector<int> adjList;
vector<int> subtreeList[100002];

int _g(int x){
    return lower_bound(timeList.begin(), timeList.end(), x) - timeList.begin();
}

void dfsSubtree(int x, int p=-1){
    subTreeSize[x] = 1;
    for(Edge y: link[x]){
        if(y.y==p || centroidUsed[y.y]) continue;
        for(int t: toggle[y.idx]) timeList.push_back(t);
        dfsSubtree(y.y, x);
        subTreeSize[x] += subTreeSize[y.y];
    }
}

int dfsFind(int x, int p, int lim){
    for(auto y: link[x]){
        if(y.y==p || centroidUsed[y.y]) continue;
        if(subTreeSize[y.y] >= lim) return dfsFind(y.y, x, lim);
    }
    return x;
}

void dfsGetList(int x, int p, vector<int> &vec){
    vec.push_back(x);
    for(auto y: link[x]){
        if(y.y==p || centroidUsed[y.y]) continue;
        dfsGetList(y.y, x, vec);
    }
}

int xtoc[100002], ctox[100002];

void update(int s, int e, int v){
    s = tree.lower_bound(1, 0, tn, s);
    e = tree.lower_bound(1, 0, tn, e+1) - 1;
    tree.update(1, 0, tn, s, e, v);
}

void dfsdp1(int x, int p, int r){ /// x���� c�� �����ϴ� ���� ���� �ð��� ���
    xtoc[x] = tree.query(1, 0, tn, 0, tn).min;
    if(xtoc[x] != tn && x!=r) ans[r]++;
    for(auto y: link[x]){
        if(y.y==p || centroidUsed[y.y]) continue;
        tree.save(); /// �� �ں��� ���׸�Ʈ Ʈ���� �����Ѵ�
        int prv = 0;
        for(int i=0; i<(int)toggle[y.idx].size(); i+=2){
            int sg = _g(toggle[y.idx][i]), eg = _g(toggle[y.idx][i+1]);
            tree.update(1, 0, tn, prv, sg, tree.query(1, 0, tn, sg, sg).min);
            prv = eg;
        }
        tree.update(1, 0, tn, prv, tn, tn);
        dfsdp1(y.y, x, r); /// ���
        tree.rollback(); /// �ѹ�
    }
}

void dfsdp2(int x, int p=-1){ /// c���� x�� ����ϴ� ���� ���� �ð��� ���
    ctox[x] = tree.lower_bound(1, 0, tn, tn) - 1;
    if(ctox[x] != -1 && p!=-1) ans[x]++;
    for(auto y: link[x]){
        if(y.y==p || centroidUsed[y.y]) continue;
        tree.save();
        int prv = 0;
        for(int i=0; i<(int)toggle[y.idx].size(); i+=2){
            int sg = _g(toggle[y.idx][i]), eg = _g(toggle[y.idx][i+1]);
            update(prv, sg, sg);
            prv = eg;
        }
        update(prv, tn, tn);
        dfsdp2(y.y, x);
        tree.rollback();
    }
}

int xtocvec[100005];
void findCentroid(int x){
    /// ���� ��Ʈ���̵带 �����, �ð��� ���� ��ǥ ������ ����.
    timeList.clear();
    dfsSubtree(x);
    x = dfsFind(x, -1, (subTreeSize[x]+1)/2);
    centroidUsed[x] = 1;
    timeList.push_back(1e9);
    sort(timeList.begin(), timeList.end());
    timeList.erase(unique(timeList.begin(), timeList.end()), timeList.end());
    tn = (int)timeList.size()-1;

    /// ���� ��Ʈ���̵忡 ������ �������� ��ϰ� �� �Ʒ��� ����Ʈ���� ����� �̾� ����.
    adjList.clear();
    for(Edge e: link[x]){
        if(centroidUsed[e.y]) continue;
        adjList.push_back(e.y);
        subtreeList[e.y].clear();
        dfsGetList(e.y, x, subtreeList[e.y]);
    }

    /// ���� ��Ʈ���̵忡������ dfs�� ���鼭, �� x�� ���� x->c�� �����ϴ� ���� ���� �ð��� ������.
    tree.init(1, 0, tn);
    dfsdp1(x, -1, x);
    tree.init(1, 0, tn);
    dfsdp2(x);

    /// �ϼ��� ctox, xtoc �迭�� ���� ���� ������ �������. (c�� ���Ե� ���� ����)
    for(Edge e: link[x]) if(!centroidUsed[e.y]) for(auto y: subtreeList[e.y]){
        xtocvec[xtoc[y]]++;
    }
    for(int i=1; i<=tn; i++) xtocvec[i] += xtocvec[i-1];
    for(Edge e: link[x]) if(!centroidUsed[e.y]) for(auto y: subtreeList[e.y]){
        ans[y] += xtocvec[ctox[y]];
    }
    for(int i=tn; i>=1; i--) xtocvec[i] -= xtocvec[i-1];
    for(Edge e: link[x]) if(!centroidUsed[e.y]) for(auto y: subtreeList[e.y]){
        xtocvec[xtoc[y]]--;
    }

    for(Edge e: link[x]) if(!centroidUsed[e.y]){
        vector<int> vec;
        for(auto y: subtreeList[e.y]) vec.push_back(xtoc[y]);
        sort(vec.begin(), vec.end());
        for(auto y: subtreeList[e.y]){
            ans[y] -= upper_bound(vec.begin(), vec.end(), ctox[y]) - vec.begin();
        }
    }

    /// ���� ��������� ����.
    for(Edge e: link[x]){
        if(centroidUsed[e.y]) continue;
        findCentroid(e.y);
    }
}

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<n; i++){
        scanf("%d %d", &ex[i], &ey[i]);
        link[ex[i]].push_back(Edge(ex[i], ey[i], i));
        link[ey[i]].push_back(Edge(ey[i], ex[i], i));
    }
    for(int i=1; i<=m; i++){
        scanf("%d", &arr[i]);
        toggle[arr[i]].push_back(i);
    }
    for(int i=1; i<=q; i++) scanf("%d", &query[i]);
    for(int i=1; i<n; i++) if(toggle[i].size() % 2) toggle[i].push_back(m+1);

    for(int i=1; i<=n; i++) ans[i] = 1;
    findCentroid(1);
    for(int i=1; i<=q; i++){
        printf("%d\n", ans[query[i]]);
    }
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:255:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  255 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:257:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  257 |         scanf("%d %d", &ex[i], &ey[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:262:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  262 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
synchronization.cpp:265:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  265 |     for(int i=1; i<=q; i++) scanf("%d", &query[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 7 ms 7508 KB Output is correct
4 Correct 7 ms 7508 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 35 ms 10108 KB Output is correct
7 Correct 608 ms 47184 KB Output is correct
8 Runtime error 353 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Incorrect 4 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -