oj.uz

Submission #200775

# Submission time Handle Problem Language Result Execution time Memory
200775 2020-02-08T06:39:38 Z ho94949 Railway Trip (JOI17_railway_trip) C++17
30 / 100
 2000 ms 12176 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 380 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 31 ms 9188 KB Output is correct
3 Correct 33 ms 9592 KB Output is correct
4 Correct 38 ms 10104 KB Output is correct
5 Correct 36 ms 10232 KB Output is correct
6 Correct 39 ms 10488 KB Output is correct
7 Correct 44 ms 10616 KB Output is correct
8 Correct 21 ms 6512 KB Output is correct
9 Execution timed out 2072 ms 2660 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 11000 KB Output is correct
2 Correct 113 ms 10872 KB Output is correct
3 Correct 118 ms 11128 KB Output is correct
4 Correct 120 ms 11128 KB Output is correct
5 Correct 127 ms 11256 KB Output is correct
6 Correct 122 ms 11256 KB Output is correct
7 Correct 113 ms 11256 KB Output is correct
8 Correct 100 ms 9120 KB Output is correct
9 Correct 78 ms 7896 KB Output is correct
10 Correct 88 ms 7900 KB Output is correct
11 Correct 85 ms 7896 KB Output is correct
12 Correct 84 ms 7904 KB Output is correct
13 Correct 84 ms 7900 KB Output is correct
14 Correct 98 ms 7804 KB Output is correct
15 Correct 116 ms 7976 KB Output is correct
16 Correct 113 ms 8440 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 12152 KB Output is correct
2 Correct 156 ms 12152 KB Output is correct
3 Correct 153 ms 12024 KB Output is correct
4 Correct 160 ms 12176 KB Output is correct
5 Correct 76 ms 7900 KB Output is correct
6 Execution timed out 2073 ms 3064 KB Time limit exceeded
7 Halted 0 ms 0 KB -