제출 #370946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
370946		79brue	Construction of Highway (JOI18_construction)	C++14	100 / 100	1283 ms	28252 KiB

construction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    int tree[400002];
    int lazy[400002]; /// 즉시 대입

    void init(int i, int l, int r){
        tree[i] = 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){
        if(!lazy[i]) return;
        if(lazy[i]) tree[i] = lazy[i];
        if(l!=r){
            lazy[i*2] = lazy[i*2+1] = lazy[i];
        }
        lazy[i] = 0;
    }

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

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

struct Fenwick{
    int n;
    int arr[100002];
    void init(int _n){
        n = _n;
        fill(arr+1, arr+_n+1, 0);
    }
    void update(int x, int val){
        while(x<=n){
            arr[x] += val;
            x += x&-x;
        }
    }
    int sum(int x){
        int ret = 0;
        while(x){
            ret += arr[x];
            x -= x&-x;
        }
        return ret;
    }
} fenwick;

int n;
int arr[100002];
int par[100002];
int qx[100002], qy[100002];
vector<int> link[100002];

int in[100002], sz[100002], idx[100002], top[100002], depth[100002], inCnt;
int LCADB[100002][20];

void dfs_sz(int x){
    LCADB[x][0] = par[x];
    sz[x] = 1;
    for(auto &y: link[x]){
        depth[y] = depth[x] + 1;
        dfs_sz(y);
        sz[x] += sz[y];
        if(sz[y] > sz[link[x][0]]) swap(y, link[x][0]);
    }
}

void dfs_hld(int x){
    in[x] = ++inCnt;
    idx[in[x]] = x;
    for(auto y: link[x]){
        top[y] = (y == link[x][0]) ? top[x] : y;
        dfs_hld(y);
    }
}

int kth_parent(int x, int k){
    for(int d=0; d<20; d++) if((k>>d)&1) x = LCADB[x][d];
    return x;
}

void renumber(){
    vector<int> tarr;
    for(int i=1; i<=n; i++) tarr.push_back(arr[i]);
    sort(tarr.begin(), tarr.end());
    tarr.erase(unique(tarr.begin(), tarr.end()), tarr.end());
    for(int i=1; i<=n; i++) arr[i] = lower_bound(tarr.begin(), tarr.end(), arr[i]) - tarr.begin() + 1;
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
    }
    renumber();
    for(int i=1; i<n; i++){
        scanf("%d %d", &qx[i], &qy[i]);
        par[qy[i]] = qx[i];
        link[qx[i]].push_back(qy[i]);
    }

    depth[1] = 1;
    dfs_sz(1);
    top[1] = 1;
    dfs_hld(1);
    tree.init(1, 1, n);

    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
    for(int i=1; i<=n; i++){
        tree.update(1, 1, n, i, i, i);
    }

    fenwick.init(n);
    for(int i=1; i<n; i++){
        vector<pair<int, int> > vec;
        int x = qx[i];
        vec.push_back(make_pair(tree.getVal(1, 1, n, in[x]), depth[x]));
        while(x){
            if(vec.back().first == tree.getVal(1, 1, n, in[top[x]])){
                x = par[top[x]];
                continue;
            }
            int MIN = depth[top[x]], MAX = depth[x], ANS = MIN;
            while(MIN <= MAX){
                int MID = (MIN + MAX) / 2;
                int kth = kth_parent(x, depth[x]-MID);
                if(vec.back().first == tree.getVal(1, 1, n, in[kth])){
                    MAX = MID - 1;
                }
                else{
                    ANS = MID;
                    MIN = MID + 1;
                }
            }

            x = kth_parent(x, depth[x]-ANS);
            vec.push_back(make_pair(tree.getVal(1, 1, n, in[x]), depth[x]));
        }

        for(int i=0; i<(int)vec.size(); i++){
            vec[i].first = arr[vec[i].first];
            vec[i].second = (i == (int)vec.size()-1) ? vec[i].second : vec[i].second - vec[i+1].second;
        }
        ll rans = 0;

        for(auto p: vec){
            rans += ll(p.second) * ll(fenwick.sum(p.first-1));
            fenwick.update(p.first, p.second);
        }
        for(auto p: vec) fenwick.update(p.first, -p.second);
        printf("%lld\n", rans);

        x = qy[i];
        while(x){
            tree.update(1, 1, n, in[top[x]], in[x], qy[i]);
            x = par[top[x]];
        }
    }
}

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

construction.cpp: In function 'int main()':
construction.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
construction.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
construction.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  122 |         scanf("%d %d", &qx[i], &qy[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84