Submission #749524

# Submission time Handle Problem Language Result Execution time Memory
749524 2023-05-28T07:02:19 Z 반딧불(#9967) Grapevine (NOI22_grapevine) C++17
0 / 100
1366 ms 163784 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segmentTree{
    int SZ;
    vector<ll> tree, lazy;

    void init(int n){
        SZ = n;
        tree.resize(n*4+1), lazy.resize(n*4+1);

        init(1, 1, n);
    }

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

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

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

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

    ll query(){
        return query(1, 1, SZ, 1, SZ);
    }
} tree[100002];

struct Line{
    int nxt, idx;
    Line(){}
    Line(int nxt, int idx): nxt(nxt), idx(idx){}
};

int n, q;
int ex[100002], ey[100002];
ll len[100002];
vector<Line> link[100002];
bool on[100002];

namespace HLD{
    struct Fenwick{
        int n;
        ll tree[100002];

        void init(int _n){
            n = _n;
            for(int i=1; i<=n; i++) tree[i] = 0;
        }

        void _add(int x, ll v){
            while(x<=n){
                tree[x] += v;
                x += x&-x;
            }
        }

        void add(int s, int e, ll v){
            _add(s, v);
            _add(e+1, -v);
        }

        ll _sum(int x){
            ll ret = 0;
            while(x){
                ret += tree[x];
                x -= x&-x;
            }
            return ret;
        }

        ll sum(int x){
            return _sum(x);
        }
    } tree;

    int par[100002];
    int in[100002], out[100002], depth[100002], inCnt;
    int LCADB[100002][20];

    void dfs(int x, int p=-1){
        in[x] = ++inCnt;
        for(Line y: link[x]){
            if(y.nxt == p) continue;
            par[y.nxt] = x;
            depth[y.nxt] = depth[x] + 1;
            dfs(y.nxt, x);
        }
        out[x] = inCnt;
    }

    void init(){
        dfs(1);
        for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
        for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];

        tree.init(n);
        for(int i=1; i<n; i++){
            int x = ex[i], y = ey[i];
            if(depth[x] < depth[y]) swap(x, y);
            /// x�� �� �Ʒ��� �ִ� ����
            tree.add(in[x], out[x], len[i]);
        }
    }

    int getLCA(int x, int y){
        if(depth[x] > depth[y]) swap(x, y);
        for(int d=0; d<20; d++) if((depth[y]-depth[x])&(1<<d)) y = LCADB[y][d];
        if(x==y) return x;
        for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
        return par[x];
    }

    ll query(int a, int b){
        int c = getLCA(a, b);
        return tree.sum(in[a]) + tree.sum(in[b]) - tree.sum(in[c])*2;
    }

    void update(int x, ll v){
        tree.add(in[x], out[x], v);
    }
}

bool centroidUsed[100002];
int centroidRoot, centroidPar[100002], centroidDepth[100002];
int subtreeSize[100002];
int sz[100002], in[100002][20], out[100002][20], depth[100002][20];
int canFindEdges[100002][20];

void getSubtreeSize(int x, int p=-1){
    subtreeSize[x] = 1;
    for(auto y: link[x]){
        if(y.nxt==p || centroidUsed[y.nxt]) continue;
        getSubtreeSize(y.nxt, x);
        subtreeSize[x] += subtreeSize[y.nxt];
    }
}

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

void eulerTourDfs(int x, int p, int d, int c){
    in[x][d] = ++sz[c];
    for(auto y: link[x]){
        if(y.nxt == p || centroidUsed[y.nxt]) continue;
        canFindEdges[y.nxt][d] = c;
        depth[y.nxt][d] = depth[x][d] + 1;
        eulerTourDfs(y.nxt, x, d, c);
    }
    out[x][d] = sz[c];
}

void putLengthDfs(int x, int p, int d, int c){
    for(auto y: link[x]){
        if(y.nxt == p || centroidUsed[y.nxt]) continue;
        tree[c].add(1, 1, sz[c], in[y.nxt][d], out[y.nxt][d], len[y.idx]);
        putLengthDfs(y.nxt, x, d, c);
    }
}

int findCentroid(int x, int d = 0){
    getSubtreeSize(x);
    x = getCentroid(x, -1, (subtreeSize[x] + 1) / 2);
    centroidUsed[x] = 1;
    centroidDepth[x] = d;

    depth[x][d] = 0;
    eulerTourDfs(x, -1, d, x);
    tree[x].init(sz[x]);

    putLengthDfs(x, -1, d, x);

    for(auto y: link[x]){
        if(centroidUsed[y.nxt]) continue;
        int tmp = findCentroid(y.nxt, d+1);
        centroidPar[tmp] = x;
    }
    return x;
}

ll getAnswer(int x){
    int c = x;
    ll ret = 1e18;
    while(c){
        ret = min(ret, HLD::query(c, x) + tree[c].query());
        c = centroidPar[c];
    }
    assert(ret <= 1e17);
    return ret;
}

void changeVertex(int x){
    int c = x;
    ll v = (on[x] ? 1e18 : -1e18);
    on[x] = !on[x];
    while(c){ /// ��Ʈ���̵带 ���ƴٴϸ� +, - ���ֱ�
        int d = centroidDepth[c];
        tree[c].add(1, 1, sz[c], in[x][d], in[x][d], v);
        c = centroidPar[c];
    }
}

void changeEdge(int idx, ll v){
    /// HLD ������ ����
    assert(idx);
    int x = ex[idx], y = ey[idx];
    if(HLD::depth[x] < HLD::depth[y]) swap(x, y);
    HLD::update(x, v - len[idx]);

    for(int d=19; d>=0; d--){ /// ��Ʈ���̵� ������ ����
        if(!canFindEdges[idx][d]) continue;
        int x = ex[idx], y = ey[idx], c = canFindEdges[idx][d];
        if(depth[x][d] < depth[y][d]) swap(x, y); /// ���� x�� �� �Ʒ���
        tree[c].add(1, 1, sz[c], in[x][d], out[x][d], v - len[idx]);
    }

    len[idx] = v;
}

int main(){
    map<pair<int, int>, int> mpEdge;
    scanf("%d %d", &n, &q);
    for(int i=1; i<n; i++){
        int x, y; ll w;
        scanf("%d %d %lld", &x, &y, &w);
        ex[i] = x, ey[i] = y, len[i] = w;
        link[x].push_back(Line(y, i));
        link[y].push_back(Line(x, i));
        mpEdge[make_pair(x, y)] = mpEdge[make_pair(y, x)] = i;
    }
    centroidRoot = findCentroid(1);
    HLD::init();

    int grapeCnt = 0;
    while(q--){
        int qt;
        scanf("%d", &qt);
        if(qt == 1){ /// Seek the nearest
            int x;
            scanf("%d", &x);
            if(!grapeCnt) puts("-1");
            else printf("%lld\n", getAnswer(x));
        }
        else if(qt == 2){ /// ���� ������Ʈ
            int x;
            scanf("%d", &x);
            grapeCnt += (on[x] ? -1 : 1);
            changeVertex(x);
        }
        else{
            int a, b; ll w;
            scanf("%d %d %lld", &a, &b, &w);
            changeEdge(mpEdge[make_pair(a, b)], w);
        }
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:258:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  258 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:261:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  261 |         scanf("%d %d %lld", &x, &y, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:273:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |         scanf("%d", &qt);
      |         ~~~~~^~~~~~~~~~~
Main.cpp:276:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  276 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
Main.cpp:282:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  282 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
Main.cpp:288:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  288 |             scanf("%d %d %lld", &a, &b, &w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 10452 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1202 ms 146156 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1125 ms 163784 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1295 ms 144548 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1366 ms 147884 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 10452 KB Output isn't correct
2 Halted 0 ms 0 KB -