Submission #50590

#	Time	Username	Problem	Language	Result	Execution time	Memory
50590		top34051	Construction of Highway (JOI18_construction)	C++17	100 / 100	861 ms	77664 KiB

construction

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;
const int maxv = 1e5;
const int inf = 1e9;

struct node {
    int l,r,val;
    node(int _l = 0, int _r = 0, int _val = 0) {
        l = _l; r = _r; val = _val;
    }
    bool operator < (node a) const {
        if(a.l!=l) return l<a.l;
        if(a.r!=r) return r<a.r;
        return val<a.val;
    }
};

int n;
int a[maxn];
vector<int> way[maxn];
pii e[maxn];

map<int,int> mp;

int par[maxn];
int sz[maxn], bigc[maxn];
int m, cid[maxn], cpos[maxn];
int csz[maxn], chead[maxn];
set<node> itv[maxn];

int tree[maxv+5];
ll res;
vector<pii> all;
vector<node> sad;

void dfs(int u, int last) {
    sz[u] = 1;
    for(auto v : way[u]) {
        if(v==last) continue;
        par[v] = u;
        dfs(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[bigc[u]]) bigc[u] = v;
    }
}

void init(int u, int last) {
    cid[u] = m; cpos[u] = ++csz[m];
    if(cpos[u]==1) chead[m] = u;
    if(bigc[u]) init(bigc[u],u);
    for(auto v : way[u]) {
        if(v==last || v==bigc[u]) continue;
        m++; init(v, u);
    }
}

void update(int x, int val) {
    if(val>0) all.push_back({x,val});
    while(x<=maxv) {
        tree[x] += val;
        x += x&-x;
    }
}

int query(int x) {
    int res = 0;
    while(x) {
        res += tree[x];
        x -= x&-x;
    }
    return res;
}

void calc(int x, int val) {
    if(val==-1) return ;
    res += (ll)query(x-1)*val;
    update(x,val);
}

ll solve(int u) {
//    printf("solving\n");
//    printf("---- solve %d\n",u);
    int x = cid[u];
//    for(auto t : itv[x]) printf("\t\t(%d, %d, %d)\n",t.l,t.r,t.val);
    auto it = (--itv[x].upper_bound(node(cpos[u],inf,inf)));
    while(it!=itv[x].end()) {
//        printf("\t\tcalc %d : [%d, %d]\n",it->val,it->l,min(cpos[u],it->r));
        calc(it->val,min(cpos[u],it->r)-it->l+1);
        if(it==itv[x].begin()) break;
        it--;
    }
    if(chead[x]!=1) solve(par[chead[x]]);
}

void go(int u, int val) {
//    printf("---- go %d : %d\n",u,val);
    int x = cid[u];
//    for(auto t : itv[x]) printf("\t\t(%d, %d, %d)\n",t.l,t.r,t.val);
    node tmp;
    for(auto it : itv[x]) {
        if(it.l>cpos[u]) break;
        tmp = it;
        sad.push_back(tmp);
    }
    for(auto t : sad) itv[x].erase(t);
    sad.clear();
    itv[x].insert(node(1,cpos[u],val));
    if(tmp.l!=0 && cpos[u]<tmp.r) itv[x].insert(node(cpos[u]+1,tmp.r,tmp.val));
    if(chead[x]!=1) go(par[chead[x]],val);
}

void cpidx() {
    int cur = 0;
    for(int i=1;i<=n;i++) mp[a[i]];
    for(auto &t : mp) t.second = ++cur;
    for(int i=1;i<=n;i++) a[i] = mp[a[i]];
}

int main() {
//    freopen("03-09.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    cpidx();
    for(int i=1;i<=n-1;i++) {
        int u,v; scanf("%d%d",&u,&v);
        way[u].push_back(v); way[v].push_back(u);
        e[i] = {u,v};
    }
    dfs(1,0);
    m = 1; init(1,0);
    for(int i=1;i<=m;i++) itv[i].insert(node(1,csz[i],-1));
//    for(int i=1;i<=n;i++) printf("%d : id = %d pos = %d (%d)\n",i,cid[i],cpos[i],chead[cid[i]]);
    go(1,a[1]);
    for(int i=1;i<=n-1;i++) {
        res = 0;
        solve(e[i].X);
        go(e[i].Y, a[e[i].Y]);
        for(auto t : all) update(t.X,-t.Y);
        all.clear();
        printf("%lld\n",res);
    }
}

Compilation message (stderr)

construction.cpp: In function 'long long int solve(int)':
construction.cpp:99:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
construction.cpp: In function 'int main()':
construction.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
construction.cpp:128:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                           ~~~~~^~~~~~~~~~~~
construction.cpp:131:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u,v; scanf("%d%d",&u,&v);
                  ~~~~~^~~~~~~~~~~~~~

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