oj.uz

Submission #66320

# Submission time Handle Problem Language Result Execution time Memory
66320 2018-08-10T08:30:59 Z FedericoS Ancient Books (IOI17_books) C++14
0 / 100
 4 ms 620 KB 
#include <iostream>
#include <algorithm>
#include "books.h"
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

int N,S;
int UFp[1000006],UFh[1000006];
ll P[1000006];
int C[1000006];
ll ans;
int c;
ll ult1,ult2=-1;
vector<pll> V;

int UFfind(int k){

    int a;
    for(a=k;a!=UFp[a];a=UFp[a]);

    UFp[k]=a;
    return a;

}

void UFunion(int x, int y){

    x=UFfind(x);
    y=UFfind(y);

    if(UFh[x]<UFh[y])
        swap(x,y);

    UFp[y]=UFp[x];
    UFh[x]=max(UFh[x],UFh[y]+1);

}

long long minimum_walk(std::vector<int> q, int s) {

    N=q.size();
    S=s;
    for(ll i=0;i<N;i++){
        P[i]=q[i];
        ans+=abs(P[i]-i);
    }
    for(int i=0;i<N;i++){
        UFp[i]=i;
        UFh[i]=1;
    }

    fill(C,C+N,-1);

    for(int i=0;i<N;i++)
        if(C[i]==-1 and (i==0 or P[i]!=i)){
            int a=P[i];
            C[i]=c;
            while(a!=i){
                C[a]=c;
                a=P[a];
            }
            c++;
        }

    for(ll i=0;i<N;i++)
        for(ll j=i-1;j>=0;j--)
            if(C[i]!=C[j] and P[i]!=i and (P[j]!=j or j==0)){
                V.push_back({i-j,i});
                break;
            }

    sort(V.begin(),V.end());

    int p=0;
    for(int g=0;g<c-1;g++){
        while(UFfind(V[p].second)==UFfind(V[p].second-V[p].first))
            p++;
        ans+=V[p].first*2;
        UFunion(V[p].second,V[p].second-V[p].first);
    }

    return ans;

}
/*
    for(int i=0;i<N;i++)
        cout<<P[i]<<" "<<C[i]<<endl;
    for(auto p:V)
        cout<<p.first<<" "<<p.second<<" "<<p.second-p.first<<endl;
*/

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Incorrect 2 ms 620 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Incorrect 2 ms 620 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Incorrect 2 ms 620 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Incorrect 2 ms 620 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -