oj.uz

답안 #425249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
425249 2021-06-12T17:28:27 Z 2fat2code 고대 책들 (IOI17_books) C++17
22 / 100
 129 ms 16416 KB 
#include "books.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 1005;

long long n, comp, viz[nmax], l_ned, r_ned, ans;
pair<long long,long long>extend[nmax];
vector<long long>cicles[nmax];
pair<long long, long long>dp[nmax][nmax];

long long compute(long long L, long long R){
    if(L <= l_ned && R >= r_ned) return 0LL;
    else{
        if(dp[L][R].sc == 1){
            return dp[L][R].fr;
        }
        else{
            dp[L][R].sc = 1;
            dp[L][R].fr = 1e18;
            if(L > 0){
                dp[L][R].fr = compute(extend[viz[L-1]].fr, max(R, extend[viz[L-1]].sc)) + 2LL;
            }
            else if(R < n - 1){
                dp[L][R].fr = min(dp[L][R].fr, compute(min(L, extend[viz[R+1]].fr), extend[viz[R+1]].sc) + 2LL);
            }
            return dp[L][R].fr;
        }
    }
}

vector<long long>nod[nmax];
bitset<nmax>vis;

void dfs1(long long s, long long val){
    vis[s] = 1;
    extend[s].fr = min(extend[s].fr, val);
    for(auto it : nod[s]){
        if(!vis[it]) dfs1(it, val);
    }
}

void dfs2(long long s, long long val){
    vis[s] = 1;
    extend[s].sc = max(extend[s].fr, val);
    for(auto it : nod[s]){
        if(!vis[it]) dfs2(it, val);
    }
}

long long minimum_walk(vector<int> p, int s) {
	n = (int)p.size();
	for(int i=0;i<n;i++){
        ans += abs(i - p[i]);
	}
	for(int i=0;i<n;i++){
        if(!viz[i]){
            ++comp;
            viz[i] = comp;
            cicles[comp].push_back(i);
            int curr = p[i];
            while(curr  !=  i){
                viz[curr] = comp;
                cicles[comp].push_back(curr);
                curr = p[curr];
            }
        }
	}
	for(int i=1;i<=comp;i++){
        sort(all(cicles[i]));
	}
	for(int i=1;i<=comp;i++){
        extend[i].fr = cicles[i][0];
        extend[i].sc = cicles[i].back();
	}
    for(int i=0;i<=n-1;i++){
        for(int j=1;j<=comp;j++){
            if(viz[i] != j){
                if(cicles[j][0] <= i && cicles[j].back() >= i && cicles[j][0] >= cicles[viz[i]][0] && cicles[j].back() <= cicles[viz[i]].back()){
                    nod[viz[i]].push_back(j);
                }
            }
        }
    }
    for(int i=1;i<=comp;i++){
        for(int j=1;j<=comp;j++){
            if(i != j){
                if(cicles[i].back() > cicles[j].back() && cicles[i][0] >= cicles[j][0] && cicles[i][0] < cicles[j].back()){
                    nod[i].push_back(j);
                    nod[j].push_back(i);
                }
                else if(cicles[i].back() < cicles[j].back() && cicles[i][0] <= cicles[j][0] && cicles[j][0] < cicles[i].back()){
                    nod[i].push_back(j);
                    nod[j].push_back(i);
                }
                else if(cicles[j][0] <= cicles[i][0] && cicles[j].back() > cicles[i].back()){
                    nod[i].push_back(j);
                }
            }
        }
    }
    vector<pair<long long,long long>>vecc;
    for(int i=1;i<=comp;i++){
        vecc.push_back({cicles[i][0], i});
    }
    sort(all(vecc));
    for(auto it : vecc){
        if(!vis[it.sc]) dfs1(it.sc, it.fr);
    }
    vis.reset();
    vecc.clear();
    for(int i=1;i<=comp;i++){
        vecc.push_back({cicles[i].back(), i});
    }
    sort(all(vecc));
    reverse(all(vecc));
    for(auto it : vecc){
        if(!vis[it.sc]) dfs2(it.sc, it.fr);
    }
	while(p[l_ned] == l_ned && s > l_ned) l_ned++;
	r_ned = n - 1;
	while(p[r_ned] == r_ned && s < r_ned) r_ned--;
	return compute(extend[viz[s]].fr, extend[viz[s]].sc) + ans;
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 4 ms 332 KB Output is correct
22 Correct 3 ms 332 KB Output is correct
23 Correct 3 ms 460 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 3 ms 460 KB Output is correct

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 4 ms 332 KB Output is correct
22 Correct 3 ms 332 KB Output is correct
23 Correct 3 ms 460 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 3 ms 460 KB Output is correct
30 Runtime error 129 ms 16416 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1484 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 4 ms 1996 KB Output is correct
5 Correct 4 ms 1740 KB Output is correct
6 Incorrect 4 ms 460 KB 3rd lines differ - on the 1st token, expected: '22140', found: '22144'
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 4 ms 332 KB Output is correct
22 Correct 3 ms 332 KB Output is correct
23 Correct 3 ms 460 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 3 ms 460 KB Output is correct
30 Runtime error 129 ms 16416 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -