답안 #292778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292778	2020-09-07T13:20:23 Z	Saboon	고대 책들 (IOI17_books)	C++17	12 / 100	24 ms	32768 KB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;

bool visited[maxn], mark[maxn];
int c[maxn];
vector<pair<int,int>> g[maxn];
ll dp[maxn];

long long MST(int src){
    ll ret = 0;
    memset(dp, 63, sizeof dp);
    dp[src] = 0;
    set<pair<ll,int>> S;
    S.insert({dp[src],src});
    while (!S.empty()){
        int v = (*S.begin()).second;
        S.erase(S.begin());
        ret += dp[v];
        for (auto [u,w] : g[v]){
            if (dp[u] > dp[v]+w){
                S.erase({dp[u],u});
                dp[u] = dp[v]+w;
                S.insert({dp[u],u});
            }
        }
    }
    return 2LL*ret;
}

long long minimum_walk(vector<int> p, int s){
	int n = p.size();
	set<int> S;
	ll answer = 0;
    for (int i = 0; i < n; i++)
        answer += abs(p[i]-i);
	int tmp = 0, Max, Min, last;
	Max = s, last = s+1;
    for (int i = s; i < n; i++){
        if (!visited[i] and p[i] != i){
            mark[i] = 1;
            int x = i;
            c[i] = i+1;
            if (i != s and i > Max){
                g[last].push_back({c[i],i-Max});
                g[c[i]].push_back({last,0});
            }
            while (!visited[x]){
                visited[x] = 1;
                c[x] = c[i];
                if (x > Max){
                    Max = x;
                    last = c[x];
                }
                x = p[x];
            }
        }
    }
    Min = s, last = s+1;
    memset(visited, 0, sizeof visited);
	for (int i = s; i >= 0; i--){
        if (!visited[i]){
            mark[i] = 1;
            int x = i;
            if (c[i] == 0)
                c[i] = i+1;
            if (i != s and i < Min){
                g[last].push_back({c[i],Min-i});
                g[c[i]].push_back({last,0});
            }
            while (!visited[x]){
                visited[x] = 1;
                c[x] = c[i];
                if (Min > x){
                    Min = x;
                    last = c[i];
                }
                x = p[x];
            }
        }
	}
	answer += MST(s+1);
	return answer;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:37:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   37 |     for (int i = 0; i < n; i++)
      |     ^~~
books.cpp:39:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   39 |  int tmp = 0, Max, Min, last;
      |  ^~~
books.cpp:39:6: warning: unused variable 'tmp' [-Wunused-variable]
   39 |  int tmp = 0, Max, Min, last;
      |      ^~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	32640 KB	Output is correct
2	Correct	21 ms	32640 KB	Output is correct
3	Correct	21 ms	32632 KB	Output is correct
4	Correct	21 ms	32640 KB	Output is correct
5	Correct	22 ms	32592 KB	Output is correct
6	Correct	22 ms	32640 KB	Output is correct
7	Correct	23 ms	32640 KB	Output is correct
8	Correct	22 ms	32640 KB	Output is correct
9	Correct	22 ms	32768 KB	Output is correct
10	Correct	24 ms	32632 KB	Output is correct
11	Correct	22 ms	32640 KB	Output is correct
12	Correct	23 ms	32640 KB	Output is correct
13	Correct	22 ms	32640 KB	Output is correct
14	Correct	22 ms	32640 KB	Output is correct
15	Correct	23 ms	32556 KB	Output is correct
16	Correct	21 ms	32640 KB	Output is correct
17	Correct	22 ms	32640 KB	Output is correct
18	Correct	22 ms	32640 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	32640 KB	Output is correct
2	Correct	21 ms	32640 KB	Output is correct
3	Correct	21 ms	32632 KB	Output is correct
4	Correct	21 ms	32640 KB	Output is correct
5	Correct	22 ms	32592 KB	Output is correct
6	Correct	22 ms	32640 KB	Output is correct
7	Correct	23 ms	32640 KB	Output is correct
8	Correct	22 ms	32640 KB	Output is correct
9	Correct	22 ms	32768 KB	Output is correct
10	Correct	24 ms	32632 KB	Output is correct
11	Correct	22 ms	32640 KB	Output is correct
12	Correct	23 ms	32640 KB	Output is correct
13	Correct	22 ms	32640 KB	Output is correct
14	Correct	22 ms	32640 KB	Output is correct
15	Correct	23 ms	32556 KB	Output is correct
16	Correct	21 ms	32640 KB	Output is correct
17	Correct	22 ms	32640 KB	Output is correct
18	Correct	22 ms	32640 KB	Output is correct
19	Correct	22 ms	32640 KB	Output is correct
20	Correct	21 ms	32640 KB	Output is correct
21	Correct	23 ms	32640 KB	Output is correct
22	Incorrect	22 ms	32640 KB	3rd lines differ - on the 1st token, expected: '2082', found: '794'
23	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	32640 KB	Output is correct
2	Correct	21 ms	32640 KB	Output is correct
3	Correct	21 ms	32632 KB	Output is correct
4	Correct	21 ms	32640 KB	Output is correct
5	Correct	22 ms	32592 KB	Output is correct
6	Correct	22 ms	32640 KB	Output is correct
7	Correct	23 ms	32640 KB	Output is correct
8	Correct	22 ms	32640 KB	Output is correct
9	Correct	22 ms	32768 KB	Output is correct
10	Correct	24 ms	32632 KB	Output is correct
11	Correct	22 ms	32640 KB	Output is correct
12	Correct	23 ms	32640 KB	Output is correct
13	Correct	22 ms	32640 KB	Output is correct
14	Correct	22 ms	32640 KB	Output is correct
15	Correct	23 ms	32556 KB	Output is correct
16	Correct	21 ms	32640 KB	Output is correct
17	Correct	22 ms	32640 KB	Output is correct
18	Correct	22 ms	32640 KB	Output is correct
19	Correct	22 ms	32640 KB	Output is correct
20	Correct	21 ms	32640 KB	Output is correct
21	Correct	23 ms	32640 KB	Output is correct
22	Incorrect	22 ms	32640 KB	3rd lines differ - on the 1st token, expected: '2082', found: '794'
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	22 ms	32640 KB	3rd lines differ - on the 1st token, expected: '3304', found: '10672'
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	32640 KB	Output is correct
2	Correct	21 ms	32640 KB	Output is correct
3	Correct	21 ms	32632 KB	Output is correct
4	Correct	21 ms	32640 KB	Output is correct
5	Correct	22 ms	32592 KB	Output is correct
6	Correct	22 ms	32640 KB	Output is correct
7	Correct	23 ms	32640 KB	Output is correct
8	Correct	22 ms	32640 KB	Output is correct
9	Correct	22 ms	32768 KB	Output is correct
10	Correct	24 ms	32632 KB	Output is correct
11	Correct	22 ms	32640 KB	Output is correct
12	Correct	23 ms	32640 KB	Output is correct
13	Correct	22 ms	32640 KB	Output is correct
14	Correct	22 ms	32640 KB	Output is correct
15	Correct	23 ms	32556 KB	Output is correct
16	Correct	21 ms	32640 KB	Output is correct
17	Correct	22 ms	32640 KB	Output is correct
18	Correct	22 ms	32640 KB	Output is correct
19	Correct	22 ms	32640 KB	Output is correct
20	Correct	21 ms	32640 KB	Output is correct
21	Correct	23 ms	32640 KB	Output is correct
22	Incorrect	22 ms	32640 KB	3rd lines differ - on the 1st token, expected: '2082', found: '794'
23	Halted	0 ms	0 KB	-

답안 #292778

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0