Submission #200775

#	Time	Username	Problem	Language	Result	Execution time	Memory
200775		ho94949	Railway Trip (JOI17_railway_trip)	C++17	30 / 100	2073 ms	12176 KiB

railway_trip

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int N, K, Q;
int L[MAXN];

enum {LEFT=0, MID=1, RIGHT=2};
struct Node
{
    int l, r, p;
    int pos; //position
    int h; //height
    int pt[3], pd[3]; //parent type, parent distance
} n[2*MAXN+10];
int tp = 0;

int last_left[MAXN], last_right[MAXN];

void build_rec(int id)
{
    int from = n[id].l, to = n[id].r, p = id, h = n[id].h;
    if(from != -1) last_left[from] = id;
    if(to != N) last_right[to] = id;
    if(to-from==1) return;
    int m_elem = *max_element(L+from+1, L+to);
    vector<int> child_ind;
    for(int i=from+1; i<=to-1; ++i)
        if(L[i] == m_elem) child_ind.push_back(i);
    for(int i=0; i<(int)child_ind.size()+1; ++i)
    {
        n[tp].l = (i==0)?from:child_ind[i-1];
        n[tp].r = (i==(int)child_ind.size())?to:child_ind[i];
        n[tp].p = p; n[tp].h = h+1; n[tp].pos = i;
        for(int t=0; t<3; ++t)
        {
            int ldist = i; if(t==RIGHT) ++ldist;
            int rdist = (int)child_ind.size()-i; if(t==LEFT) ++rdist;
            if(ldist < rdist)
                n[tp].pt[t] = LEFT, n[tp].pd[t] = ldist;
            else if(ldist == rdist)
                n[tp].pt[t] = MID, n[tp].pd[t] = ldist;
            else
                n[tp].pt[t] = RIGHT, n[tp].pd[t] = rdist;
        }
        build_rec(tp++);
    }
}

int calc_dist(int aind, int atype, int bind, int btype)
{
    if(aind == bind)
    {
        if(atype==LEFT&&btype==RIGHT) return 1;
        else return 0;
    }
    int ans1 = n[bind].pos-n[aind].pos-1;
    if(atype==LEFT) ++ans1;
    if(btype==RIGHT) ++ans1;
    
    if(n[aind].p == 0) return ans1;

    return min(ans1,
        n[aind].pd[atype] + n[bind].pd[btype] + 
        (n[aind].pt[atype] == LEFT && n[bind].pt[btype] == RIGHT)
    );

}
int dist(int a, int b)
{
    if(a>b) swap(a, b);
    int aind = last_left[a], atype = LEFT;
    int bind = last_right[b], btype = RIGHT;
    int dv = 0;
    while(n[aind].p != n[bind].p) //until they are sibling rel
    {
        if(n[aind].h < n[bind].h)
        {
            //take b parent
            int nbind = n[bind].p;
            int nbtype = n[bind].pt[btype];
            dv += n[bind].pd[btype];
            bind = nbind; btype = nbtype;
        }
        else
        {
            //take a parent
            int naind = n[aind].p;
            int natype = n[aind].pt[atype];
            dv += n[aind].pd[atype];
            aind = naind; atype = natype;
        }
    }
    return calc_dist(aind, atype, bind, btype)+dv;
}

void build()
{
    n[tp].l = -1; n[tp].r = N; n[tp].p = -1; n[tp].h = 0;
    build_rec(tp++);
}
int main()
{
    scanf("%d%d%d", &N, &K, &Q);
    for(int i=0; i<N; ++i)
        scanf("%d", L+i);
    build();
    while(Q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", dist(a-1, b-1)-1);
    }
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &K, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", L+i);
         ~~~~~^~~~~~~~~~~
railway_trip.cpp:110: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: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3: 25 / 25
• Subtask 4: 0 / 55