oj.uz

Submission #200778

# Submission time Handle Problem Language Result Execution time Memory
200778 2020-02-08T06:41:17 Z ho94949 Railway Trip (JOI17_railway_trip) C++17
30 / 100
 2000 ms 10744 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[4*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 5 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 7 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 376 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 540 KB Output is correct
2 Correct 41 ms 9136 KB Output is correct
3 Correct 36 ms 9592 KB Output is correct
4 Correct 38 ms 9976 KB Output is correct
5 Correct 39 ms 10104 KB Output is correct
6 Correct 38 ms 10360 KB Output is correct
7 Correct 51 ms 10360 KB Output is correct
8 Correct 21 ms 6512 KB Output is correct
9 Execution timed out 2083 ms 2380 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 9848 KB Output is correct
2 Correct 118 ms 9696 KB Output is correct
3 Correct 131 ms 9976 KB Output is correct
4 Correct 116 ms 9976 KB Output is correct
5 Correct 128 ms 10140 KB Output is correct
6 Correct 150 ms 10104 KB Output is correct
7 Correct 127 ms 10104 KB Output is correct
8 Correct 97 ms 7820 KB Output is correct
9 Correct 76 ms 6752 KB Output is correct
10 Correct 89 ms 6792 KB Output is correct
11 Correct 94 ms 6748 KB Output is correct
12 Correct 104 ms 6832 KB Output is correct
13 Correct 105 ms 6724 KB Output is correct
14 Correct 101 ms 6692 KB Output is correct
15 Correct 110 ms 6648 KB Output is correct
16 Correct 148 ms 7424 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 10616 KB Output is correct
2 Correct 182 ms 10716 KB Output is correct
3 Correct 209 ms 10744 KB Output is correct
4 Correct 182 ms 10616 KB Output is correct
5 Correct 86 ms 6748 KB Output is correct
6 Execution timed out 2073 ms 2368 KB Time limit exceeded
7 Halted 0 ms 0 KB -