Submission #1253335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253335		aren_dance	Ancient Books (IOI17_books)	C++20	0 / 100	23 ms	47428 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();
	for(int i=0;i<n;++i){
	    g[i].push_back(p[i]);
	    g_rev[p[i]].push_back(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;
	for(auto i:order){
	    dfs2(i,comp);
	    ++comp;
	}
	vector<pair<long long,long long>> st(n+1,{1e9,0}); 
	for(long long i=0;i<n;++i){
	    st[id[i]].second=i;
	    st[id[i]].first=min(st[id[i]].first,i);
	}
	long long answ=0ll;
	long long last=0ll;
	for(int i=0;i<comp-1;++i){
	    answ+=2*(st[i].second-st[i].first);
	    answ+=(st[i].first-last);
	    last=st[i].first;
	}
	answ+=last;
	return answ;
}

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