Submission #1253403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253403		aren_dance	Ancient Books (IOI17_books)	C++20	12 / 100	28 ms	47448 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const int N=1e6+1;
vector<int> order;
vector<int> g[N];
vector<int> g_rev[N];
bool vis[N];
int id[N];
void dfs1(int node){
    vis[node]=1;
    for(auto i:g[node]){
        if(!vis[i])
        dfs1(i);
    }
    order.push_back(node);
}
void dfs2(int node,int comp){
    id[node]=comp;
    vis[node]=1;
    for(auto i:g_rev[node]){
        if(!vis[i])
        dfs2(i,comp);
    }
}
long long minimum_walk(std::vector<int> p, int s) {
	int n=p.size();
	vector<int> k(n);
	for(int i=0;i<n;++i){
	    g[p[i]].push_back(i);
	    g_rev[i].push_back(p[i]);
	    k[p[i]]=i;
	}
	for(int i=0;i<n;++i){
	    if(!vis[i])
	    dfs1(i);
	}
	for(int i=0;i<n;++i){
	    vis[i]=0;
	}
	reverse(order.begin(),order.end());
	int comp=0;
	long long h=0ll;
	for(auto i:order){
	    if(!vis[i]){
	        dfs2(i,comp);
	        ++comp;
	    }
	}
	for(int i=0;i<n;++i){
	    vis[i]=0;
	}
	vector<int> kar(n,0);
	vector<int> bl(n+1);
	for(int i=0;i<n;++i){
	    kar[id[i]]++;
	    bl[id[i]]=i;
	}
	int mx=-1;
	for(int i=0;i<n;++i){
	    if(!vis[id[i]] && kar[id[i]]>=2 && mx<i){
	        h=i;
	        vis[id[i]]=1;
	        mx=bl[id[i]];
	        break;
	    }
	}
	long long answ=2*h;
	vector<vector<int>> r(comp);
	for(int i=0;i<n;++i){
	    answ+=abs(i-k[i]);
	}
	return answ;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30