oj.uz

Submission #45411

# Submission time Handle Problem Language Result Execution time Memory
45411 2018-04-13T08:36:40 Z Extazy Construction of Highway (JOI18_construction) C++17
0 / 100
 61 ms 70256 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 100007;

int n,a[N];
vector < int > v[N];
pair < int, int > e[N];
int size_of_subtree[N];
deque < pair < int, int > > d[N];
int chains,chain_of_node[N],head_of_chain[N],index_in_chain[N],parent[N];
int it[N];
int p[N];
map < int, int > code;
int all;

void update(int pos, int value) {
    for(;pos<=all;pos+=pos&(-pos)) it[pos]+=value;
}

int query(int pos) {
    int ans=0;
    for(;pos>=1;pos-=pos&(-pos)) ans+=it[pos];
    return ans;
}

void dfs(int node) {
    size_of_subtree[node]=1;
    if(v[node].empty()) return;

    int i,max_size=-1,which=-1;

    for(i=0;i<(int)(v[node].size());i++) {
        dfs(v[node][i]);
        size_of_subtree[node]+=size_of_subtree[v[node][i]];
        
        if(size_of_subtree[v[node][i]]>max_size) {
            max_size=size_of_subtree[v[node][i]];
            which=i;
        }
    }

    swap(v[node][0],v[node][which]);
}

void build_hld(int node, int chain, int idx) {
    chain_of_node[node]=chain;
    index_in_chain[node]=idx;

    if(v[node].empty()) return;

    int i;

    build_hld(v[node][0],chain,idx+1);
    for(i=1;i<(int)(v[node].size());i++) {
        head_of_chain[++chains]=v[node][i];
        build_hld(v[node][i],chains,1);
    }
}

void append(int chain, int value) {
    if(!d[chain].empty() && d[chain].back().first==value) {
        ++d[chain][d[chain].size()-1].second;
    }
    else {
        d[chain].push_back(make_pair(value,1));
    }
}

void extract(deque < pair < int, int > > d, int cnt, vector < pair < int, int > > &f) {
    int i;
    vector < pair < int, int > > v;

    for(i=0;i<(int)(d.size()) && cnt>0;i++) {
        int curr=min(cnt,d[i].second);
        cnt-=curr;
        v.push_back(make_pair(d[i].first,curr));
    }

    reverse(v.begin(),v.end());
    for(i=0;i<(int)(v.size());i++) f.push_back(v[i]);
}

long long count_inversions(int node) {
    vector < pair < int, int > > v;
    long long ans=0;
    int i;

    while(node) {
        extract(d[chain_of_node[node]],index_in_chain[node],v);
        node=parent[head_of_chain[chain_of_node[node]]];
    }

    for(i=0;i<(int)(v.size());i++) {
        ans+=query(v[i].first)*1ll*v[i].second;
        update(v[i].first,v[i].second);
    }

    for(i=0;i<(int)(v.size());i++) {
        update(v[i].first,-v[i].second);
    }

    return ans;
}

void eliminate(deque < pair < int, int > > &d, int cnt) {
    while(!d.empty() && cnt>=d.front().second) {
        cnt-=d.front().second;
        d.pop_front();
    }
    if(cnt>0) d[0].second-=cnt;
}

void assign(int node, int value) {
    while(node) {
        eliminate(d[chain_of_node[node]],index_in_chain[node]);
        if(!d[chain_of_node[node]].empty() && d[chain_of_node[node]].front().first==value) {
            d[chain_of_node[node]][0].second+=index_in_chain[node];
        }
        else {
            d[chain_of_node[node]].push_front(make_pair(value,index_in_chain[node]));
        }

        node=parent[head_of_chain[chain_of_node[node]]];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i;

    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        scanf("%d", &a[i]);
        p[i]=a[i];
    }

    sort(p+1,p+1+n);
    code[p[1]]=1;
    for(i=2;i<=n;i++) if(p[i]!=p[i-1]) {
        code[p[i]]=code[p[i-1]]+1;
    }
    all=code[p[n]];
    
    for(i=1;i<=n;i++) {
        a[i]=code[a[i]];
    }

    for(i=1;i<n;i++) {
        scanf("%d %d", &e[i].first, &e[i].second);
        parent[e[i].second]=e[i].first;
        v[e[i].first].push_back(e[i].second);
    }
    
    dfs(1);

    chains=1;
    head_of_chain[1]=1;
    build_hld(1,1,1);

    append(1,a[1]);

    for(i=1;i<n;i++) {
        printf("%lld\n", count_inversions(e[i].first));
        append(chain_of_node[e[i].second],a[e[i].second]);
        assign(e[i].second,a[e[i].second]);
    }

    return 0;
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:135:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
construction.cpp:153:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &e[i].first, &e[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 70008 KB Output is correct
2 Correct 61 ms 70256 KB Output is correct
3 Incorrect 60 ms 70256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 70008 KB Output is correct
2 Correct 61 ms 70256 KB Output is correct
3 Incorrect 60 ms 70256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 70008 KB Output is correct
2 Correct 61 ms 70256 KB Output is correct
3 Incorrect 60 ms 70256 KB Output isn't correct
4 Halted 0 ms 0 KB -