oj.uz

답안 #241067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
241067 2020-06-22T12:55:48 Z osaaateiasavtnl Railway Trip (JOI17_railway_trip) C++14
30 / 100
 2000 ms 11376 KB 
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
 
const int N = 1e5+7, INF = 1e9+7;
int n, k, q;
int a[N], ans[N];
int pref[N], suff[N];
int newl[N], newr[N];
vector <int> pos[N];

int par[N];
int root(int u) {
    if (par[u] == u)
        return u;
    else
        return par[u] = root(par[u]);
}
void merge(int u, int v) {
    u = root(u);
    v = root(v);
    if (u != v) {
        par[u] = v;
    }
}   

int link_l[N], link_r[N];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> k >> q; 
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
 
    vector <ii> d;
    for (int i = 0; i < q; ++i) {
        int u, v;
        cin >> u >> v;
        if (v < u)
            swap(u, v);
        d.app(mp(u, v));            
        ans[i] = INF;
    }   

    for (int i = 1; i <= k; ++i)
        pos[i].app(0);    
    for (int i = 1; i <= n; ++i)
        pos[a[i]].app(i);
    for (int i = 1; i <= k; ++i)
        pos[i].app(n+1);

    for (int i = 1; i <= n; ++i)
        par[i] = i;

    auto same_dist = [&](int i, int j) {
        int p1 = lower_bound(all(pos[a[i]]), i) - pos[a[i]].begin();
        int p2 = lower_bound(all(pos[a[j]]), j) - pos[a[j]].begin();
        return abs(p1-p2);
    };

    for (int x = 1; x <= k; ++x) {
        //cout << "x " << x << endl;

        for (int i : pos[x]) {
            if (i && a[i - 1] <= x) {
                merge(i, i - 1);
            }   
            if (i + 1 <= n && a[i + 1] <= x) {
                merge(i, i + 1);
            }   
        }

        memset(link_l, 0, sizeof link_l);
        memset(link_r, 0, sizeof link_r);
        for (int i = 1; i <= n; ++i)
            newl[i] = newr[i] = INF;

        for (int i : pos[x]) {
            link_l[i] = link_r[i] = i;
            newl[i] = newr[i] = 0;
            for (int j = i - 1; j; --j) {
                if (a[j] >= a[i])
                    break;
                newr[j] = suff[j]+1;
                link_r[j] = i;
            }   
            for (int j = i + 1; j <= n; ++j) {
                if (a[j] >= a[i])
                    break;
                newl[j] = pref[j]+1;
                link_l[j] = i;
            }
        }   

        for (int i = 1; i <= n; ++i) {
            newl[i] = min(newl[i], newr[i]+1);
            newr[i] = min(newr[i], newl[i]+1);
        }   
        
        //pref - dist to nearest prefix maximum
        //suff - dist to nearest suffix maximum
        //newl - dist to nearest left x
        //newr - dist to nearest right x
        //link_l = number of the nearest left x

        int lf = 0;
        for (int i = 1; i <= n; ++i) {
            if (a[i] > x) {
                lf = i;
                continue;
            }
            auto t = upper_bound(all(pos[x]), lf);
            if (*t <= i) {
                auto link = prev(upper_bound(all(pos[x]), i));
                pref[i] = newl[i] + (link - t);
            }   
            else if (link_r[i]) {
                pref[i] = min(pref[i], newr[i]);
            }   
        }   

        int rf = n+1;
        for (int i = n; i; --i) {
            if (a[i] > x) {
                rf = i;
                continue;
            }   
            auto t = prev(upper_bound(all(pos[x]), rf));
            if (*t >= i) {
                auto link = lower_bound(all(pos[x]), i);
                suff[i] = newr[i] + (t - link);
            }   
            else if (link_l[i]) {
                suff[i] = min(suff[i], newl[i]);
            }   
        }   

        for (int i = 0; i < q; ++i) {
            int u = d[i].f, v = d[i].s;
            if (root(u) == root(v)) {
                if (link_l[u] && link_l[v]) {
                    ans[i] = min(ans[i], newl[u] + newl[v] + same_dist(link_l[u], link_l[v]));
                }
                if (link_l[u] && link_r[v]) {
                    ans[i] = min(ans[i], newl[u] + newr[v] + same_dist(link_l[u], link_r[v]));
                }
                if (link_r[u] && link_l[v]) {
                    ans[i] = min(ans[i], newr[u] + newl[v] + same_dist(link_r[u], link_l[v]));
                }
                if (link_r[u] && link_r[v]) {
                    ans[i] = min(ans[i], newr[u] + newr[v] + same_dist(link_r[u], link_r[v]));
                }
            }
        }   
    }       

    for (int i = 0; i < q; ++i)
        cout << ans[i] - 1 << endl;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 3584 KB Output is correct
2 Correct 9 ms 3584 KB Output is correct
3 Correct 9 ms 3456 KB Output is correct
4 Correct 9 ms 3456 KB Output is correct
5 Correct 9 ms 3584 KB Output is correct
6 Correct 10 ms 3456 KB Output is correct
7 Correct 9 ms 3456 KB Output is correct
8 Correct 7 ms 3456 KB Output is correct
9 Correct 6 ms 3456 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 3584 KB Output is correct
2 Correct 88 ms 6768 KB Output is correct
3 Correct 124 ms 6904 KB Output is correct
4 Correct 206 ms 6776 KB Output is correct
5 Correct 329 ms 6732 KB Output is correct
6 Execution timed out 2079 ms 6784 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 8104 KB Output is correct
2 Correct 210 ms 9708 KB Output is correct
3 Correct 238 ms 9456 KB Output is correct
4 Correct 240 ms 9580 KB Output is correct
5 Correct 241 ms 9712 KB Output is correct
6 Correct 247 ms 9584 KB Output is correct
7 Correct 257 ms 9580 KB Output is correct
8 Correct 204 ms 10480 KB Output is correct
9 Correct 207 ms 11268 KB Output is correct
10 Correct 275 ms 10864 KB Output is correct
11 Correct 317 ms 11376 KB Output is correct
12 Correct 298 ms 10864 KB Output is correct
13 Correct 294 ms 10776 KB Output is correct
14 Correct 199 ms 10212 KB Output is correct
15 Correct 215 ms 9712 KB Output is correct
16 Correct 257 ms 9456 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2083 ms 10608 KB Time limit exceeded
2 Halted 0 ms 0 KB -