oj.uz

Submission #718761

# Submission time Handle Problem Language Result Execution time Memory
718761 2023-04-04T17:37:09 Z Jarif_Rahman Ancient Books (IOI17_books) C++17
12 / 100
 3 ms 228 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct dsu{
    int n;
    vector<int> sz, p;
    dsu(int nn){
        n = nn;
        sz.resize(n, 1);
        p.resize(n);
        for(int i = 0; i < n; i++) p[i] = i;
    }
    int get(int x){
        if(p[x] != x) p[x] = get(p[x]);
        return p[x];
    }
    void unite(int a, int b){
        a = get(a), b  = get(b);
        if(a == b) return;
        if(sz[b] > sz[a]) swap(a, b);
        sz[a]+=sz[b];
        sz[b] = 0;
        p[b] = a;
    }
};
 
ll minimum_walk(vector<int> p, int s){
    int n = p.size();
    ll ans = 0;
 
    vector<int> C(n, -1), sz;
    int k = 0;
    for(int i = 0; i < n; i++){
        if(C[i] != -1) continue;
        int x = p[i];
        C[i] = k;
        sz.pb(1);
        ans+=abs(i-x);
        while(x != i){
            C[x] = k;
            sz.back()++;
            ans+=abs(p[x]-x);
            x = p[x];
        }
        k++;
    }

    for(int x: C) cerr << x << " ";
    cerr << "d\n";

    vector<int> first(k, -1), last(k);
    for(int i = 0; i < n; i++){
        if(first[C[i]] == -1) first[C[i]] = i;
        last[C[i]] = i;
    }

    vector<bool> unnecessary(k, 0);
    for(int i = 0; i < n; i++){
        if(sz[C[i]] > 1 || i == s) break;
        unnecessary[C[i]] = 1;
    }
    for(int i = n-1; i >= 0; i--){
        if(sz[C[i]] > 1 || i == s) break;
        unnecessary[C[i]] = 1;
    }

    dsu ds(k);
    /*for(int i = 0; i < k; i++) for(int j = i+1; j < k; j++){
        if(unnecessary[i] || unnecessary[j]) continue;
        if(last[i] < first[j] || first[i] > last[j]) continue;
        ds.unite(i, j);
    }*/
    for(int i = 0; i+1 < n; i++){
        if(unnecessary[C[i]] || unnecessary[C[i+1]]) continue;
        if(last[C[i]] < first[C[i+1]] || first[C[i]] > last[C[i+1]]) continue;
        ds.unite(C[i], C[i+1]);
    }

    for(int i = 0; i+1 < n; i++){
        if(unnecessary[C[i]] || unnecessary[C[i+1]]) continue;
        if(ds.get(C[i]) != ds.get(C[i+1])) ds.unite(C[i], C[i+1]), ans+=2;
    }

    return ans;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 228 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 228 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 3 ms 212 KB Output is correct
20 Correct 3 ms 212 KB Output is correct
21 Correct 3 ms 212 KB Output is correct
22 Incorrect 3 ms 212 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2084'
23 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 228 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 3 ms 212 KB Output is correct
20 Correct 3 ms 212 KB Output is correct
21 Correct 3 ms 212 KB Output is correct
22 Incorrect 3 ms 212 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2084'
23 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 212 KB 3rd lines differ - on the 1st token, expected: '3304', found: '4062'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 228 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 3 ms 212 KB Output is correct
20 Correct 3 ms 212 KB Output is correct
21 Correct 3 ms 212 KB Output is correct
22 Incorrect 3 ms 212 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2084'
23 Halted 0 ms 0 KB -