Submission #292777

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
292777	2020-09-07T13:18:24 Z	Saboon	Ancient Books (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;
            if (i != s and i > Max)
                g[last].push_back({i+1,i-Max});
            c[i] = i+1;
            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 (i != s and i < Min)
                g[last].push_back({i+1,Min-i});
            if (c[i] == 0)
                c[i] = i+1;
            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

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	32632 KB	Output is correct
2	Correct	21 ms	32768 KB	Output is correct
3	Correct	22 ms	32640 KB	Output is correct
4	Correct	21 ms	32640 KB	Output is correct
5	Correct	22 ms	32640 KB	Output is correct
6	Correct	22 ms	32640 KB	Output is correct
7	Correct	21 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	21 ms	32640 KB	Output is correct
11	Correct	22 ms	32640 KB	Output is correct
12	Correct	23 ms	32640 KB	Output is correct
13	Correct	21 ms	32640 KB	Output is correct
14	Correct	21 ms	32640 KB	Output is correct
15	Correct	22 ms	32640 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	32632 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	32632 KB	Output is correct
2	Correct	21 ms	32768 KB	Output is correct
3	Correct	22 ms	32640 KB	Output is correct
4	Correct	21 ms	32640 KB	Output is correct
5	Correct	22 ms	32640 KB	Output is correct
6	Correct	22 ms	32640 KB	Output is correct
7	Correct	21 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	21 ms	32640 KB	Output is correct
11	Correct	22 ms	32640 KB	Output is correct
12	Correct	23 ms	32640 KB	Output is correct
13	Correct	21 ms	32640 KB	Output is correct
14	Correct	21 ms	32640 KB	Output is correct
15	Correct	22 ms	32640 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	32632 KB	Output is correct
19	Correct	22 ms	32640 KB	Output is correct
20	Correct	22 ms	32640 KB	Output is correct
21	Correct	22 ms	32640 KB	Output is correct
22	Incorrect	24 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	32632 KB	Output is correct
2	Correct	21 ms	32768 KB	Output is correct
3	Correct	22 ms	32640 KB	Output is correct
4	Correct	21 ms	32640 KB	Output is correct
5	Correct	22 ms	32640 KB	Output is correct
6	Correct	22 ms	32640 KB	Output is correct
7	Correct	21 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	21 ms	32640 KB	Output is correct
11	Correct	22 ms	32640 KB	Output is correct
12	Correct	23 ms	32640 KB	Output is correct
13	Correct	21 ms	32640 KB	Output is correct
14	Correct	21 ms	32640 KB	Output is correct
15	Correct	22 ms	32640 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	32632 KB	Output is correct
19	Correct	22 ms	32640 KB	Output is correct
20	Correct	22 ms	32640 KB	Output is correct
21	Correct	22 ms	32640 KB	Output is correct
22	Incorrect	24 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

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

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	32632 KB	Output is correct
2	Correct	21 ms	32768 KB	Output is correct
3	Correct	22 ms	32640 KB	Output is correct
4	Correct	21 ms	32640 KB	Output is correct
5	Correct	22 ms	32640 KB	Output is correct
6	Correct	22 ms	32640 KB	Output is correct
7	Correct	21 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	21 ms	32640 KB	Output is correct
11	Correct	22 ms	32640 KB	Output is correct
12	Correct	23 ms	32640 KB	Output is correct
13	Correct	21 ms	32640 KB	Output is correct
14	Correct	21 ms	32640 KB	Output is correct
15	Correct	22 ms	32640 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	32632 KB	Output is correct
19	Correct	22 ms	32640 KB	Output is correct
20	Correct	22 ms	32640 KB	Output is correct
21	Correct	22 ms	32640 KB	Output is correct
22	Incorrect	24 ms	32640 KB	3rd lines differ - on the 1st token, expected: '2082', found: '794'
23	Halted	0 ms	0 KB	-

Submission #292777

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