제출 #171775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171775		balbit	Construction of Highway (JOI18_construction)	C++14	7 / 100	13 ms	9976 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i=(n-1); i>=0; --i)
#define REP1(i,n) FOR(i,1,n+1)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;


void GG(){cout<<"-1\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b) % mo;
}

const int maxn = 1e5+5;

struct BIT{
    vector<ll> s;
    int MX=0;
    ll QU(int e){
        ll re = 0; e ++;
        while (e>0) {
            re+=s[e]; e-=e&(-e);
        }return re;
    }
    void MO(int e, ll v){
        e++; while (e<MX){
            s[e]+=v; e+=e&(-e);
        }
    }
    BIT(int _mx){
        MX = _mx; s.resize(MX+1);
    }
};

int top[maxn]; // Lowest depth for this color
int rt[maxn]; // Rightmost child in its sub tree
int at1[maxn], at2[maxn]; // Position for each node in euler tour 1, euler tour 2
int fa[21][maxn], dep[maxn];

int it1 = 0, it2 = 0;
vector<int> g[maxn];
void dfs(int v, int p) {
    at1[v] = it1++;
    rt[v] = v;
    for (int u : g[v]) {
        if (u != p) {
            dep[u] = dep[v]+1; fa[0][u]= v;
            dfs(u,v);
            rt[v] = rt[u];
        }
    }
    at2[v] = it2++;
}

int C[maxn];
BIT b1 (maxn), b2(maxn);
vector<int> order;

int kth(int a, int k) {
    for (int j = 0; k!=0; j++,k/=2) {
        if (k&1) a = fa[j][a];
    }
    return a;
}


inline void upd(int a, int v) { // Change all ancestors of a (including a) by v
    b1.MO(0,v); b2.MO(0,v);
    b1.MO(at1[rt[a]]+1,-v);
    b2.MO(at2[a],-v);
}

inline int val(int a){
    return b1.QU(at1[a])-b2.QU(at2[a]);
}

BIT invbit(maxn+100);
ll inversions(vector<pii> &a){
    ll re = 0;
    for (pii ele : a) {
        re += invbit.QU(ele.f-1) * ele.s;
        invbit.MO(ele.f,ele.s);
    }
    for (pii ele : a) {
        invbit.MO(ele.f,-ele.s);
    }
    return re;
}

signed main(){
    IOS();
#ifdef BALBIT
freopen("input.in","r",stdin);
#endif // BALBIT
    int n; cin>>n;
    assert(n<=500);
    vector<int> tmpc(n);
    REP(i,n) cin>>tmpc[i];
    vector<int> tmpc2 = tmpc;
    sort(ALL(tmpc));
    REP(i,n) C[i] = lower_bound(ALL(tmpc), tmpc2[i]) - tmpc.begin();
    REP(i,n-1) {
        int a, b; cin>>a>>b; a--; b--; g[a].pb(b); order.pb(b);
    }
    dfs(0,-1);
    FOR(j,1,21) REP(i,n) {
        fa[j][i] = fa[j-1][fa[j-1][i]];
    }
    fill(top, top+n, 10000000); top[0] = 0; // 1 is already in place
    for (int B : order){
        bug(B);
        vector<pii> met; // C-values
        upd(B,B);
        int chg = B;
        int tocol = B;
        while (B != 0){
            int p = fa[0][B];
            int pval = val(p) - chg;
            bug(pval);
            int odep = dep[B];
            int addto = tocol-pval-chg;
            chg += addto;
            upd(p, addto);
            int totop = top[pval];
            top[pval] = dep[B];
            B = kth(B, dep[B]-totop);
            met.pb({C[pval],odep-dep[B]});
            bug(B);
        }
        top[tocol] = 0;

//#ifdef BALBIT
//        REP(i,n) {
//            bug(i+1, val(i));
//        }
//        for (pii item : met) {
//            cout<<item.f<<' '<<item.s<<endl;
//        }
//        cout<<"====="<<endl;
//#endif
        cout<<inversions(met)<<"\n";
    }

}

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