oj.uz

Submission #92020

# Submission time Handle Problem Language Result Execution time Memory
92020 2019-01-01T05:42:33 Z Retro3014 Construction of Highway (JOI18_construction) C++17
0 / 100
 4 ms 2808 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;
#define MAX_N 100000
typedef long long ll;

int N;
int C[MAX_N+1];
int idx[MAX_N+1];
int lv[MAX_N+1];
int par[MAX_N+1][30];
int a, b;
int in[MAX_N+1], out[MAX_N+1];
vector<int> gp[MAX_N+1];
vector<int> query;
deque<pair<int, int>> dq;

int two=1, two2=1;
int seg[MAX_N*4+1];
int seg2[MAX_N*4+1];

int t=1;
void dfs(int x){
    in[x]=t++;
    for(int i=0; i<gp[x].size(); i++){
        dfs(gp[x][i]);
    }
    out[x]=t++;
}

void update2(int x, int y){
    x+=two2; while(x>0) {seg2[x]=max(seg2[x], y); x/=2;}
}
int find_max(int x, int y){
    x+=two2; y+=two2;
    int ret=0;
    while(x<=y){
        if(x==y)    return max(ret, seg2[x]);
        if(x%2) ret=max(ret, seg2[x++]);
        if(!(y%2))  ret=max(ret, seg2[y--]);
        x/=2; y/=2;
    }
    return ret;
}

vector<int> used;
void update(int x, int y){
    x+=two; used.push_back(x);   while(x>0)  {seg[x]+=y; x/=2;}
}void init(){
    int x;
    while(!used.empty())    {x=used.back(); used.pop_back(); while(x>0){seg[x]=0; x/=2;}}
}
int sum(int x, int y){
    int ret=0;  x+=two; y+=two;
    while(x<=y){if(x==y){return ret+seg[x];}
        if(x%2) ret+=seg[x++];
        if(!(y%2))ret+=seg[y--];
        x/=2; y/=2;
    }return ret;
}
int sum(int x){return sum(0, x);}



pair<int, int> group[MAX_N+1];

int find_up(int x, int level){
    if(lv[x]==level)    return x;
    int t=0;
    while(par[x][t+1]!=0 && lv[par[x][t+1]]>=level) t++;
    return find_up(par[x][t], level);
}

int main(){
    freopen("sample-in-01.txt", "r", stdin);
    scanf("%d", &N);    while(two<=N)   two*=2;
    two2=two*2-1;
    for(int i=1; i<=N; i++){
        scanf("%d", &C[i]);
        dq.push_back(make_pair(C[i], i));
    }
    sort(dq.begin(), dq.end());
    for(int i=0; i<dq.size(); i++){
        if(i!=0 && dq[i].first==dq[i-1].first){
            idx[dq[i].second]=idx[dq[i-1].second];
        }else if(i!=0){
            idx[dq[i].second]=idx[dq[i-1].second]+1;
        }else{
            idx[dq[i].second]=0;
        }
    }
    query.push_back(1);
    for(int i=1; i<N; i++){
        scanf("%d%d", &a, &b);
        query.push_back(b);
        gp[a].push_back(b);
        par[b][0]=a; lv[b]=lv[a]+1;
        int t=0;
        while(par[par[b][t]][t]!=0){
            par[b][t+1]=par[par[b][t]][t];  t++;
        }
    }
    dfs(1);
    update2(in[1], 0); update2(out[1], 0);
    group[1]=make_pair(0, 0);
    ll ans;
    for(int i=1; i<query.size(); i++){
        ans=0;
        init();
        int t=par[query[i]][0], tmp;
        int gt;
        while(t!=0){
            gt=query[find_max(in[t], out[t])];
            ans+=(ll)sum(idx[gt]-1) * (lv[t]-group[gt].first+1);
            update(idx[gt], lv[t]-group[gt].first+1);
            if(group[gt].first !=0)  tmp=find_up(gt, group[gt].first-1);
            else{
                group[gt].first=lv[t]+1; break;
            }
            group[gt].first = lv[t]+1;
            t=tmp;
        }
        printf("%lld\n", ans);
        update2(in[query[i]], i); update2(out[query[i]], i);
    }
    
    return 0;
}

Compilation message

construction.cpp: In function 'void dfs(int)':
construction.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gp[x].size(); i++){
                  ~^~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<dq.size(); i++){
                  ~^~~~~~~~~~
construction.cpp:110:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<query.size(); i++){
                  ~^~~~~~~~~~~~~
construction.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("sample-in-01.txt", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);    while(two<=N)   two*=2;
     ~~~~~^~~~~~~~~~
construction.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &C[i]);
         ~~~~~^~~~~~~~~~~~~
construction.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -