oj.uz

Submission #292772

# Submission time Handle Problem Language Result Execution time Memory
292772 2020-09-07T13:13:37 Z Saboon Ancient Books (IOI17_books) C++17
0 / 100
 23 ms 32640 KB 
#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 = -1, last = -1;
    for (int i = s; i < n; i++){
        if (!visited[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 = n, last = -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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32640 KB Output is correct
2 Correct 22 ms 32640 KB Output is correct
3 Correct 23 ms 32640 KB Output is correct
4 Correct 22 ms 32636 KB Output is correct
5 Incorrect 23 ms 32640 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32640 KB Output is correct
2 Correct 22 ms 32640 KB Output is correct
3 Correct 23 ms 32640 KB Output is correct
4 Correct 22 ms 32636 KB Output is correct
5 Incorrect 23 ms 32640 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32640 KB Output is correct
2 Correct 22 ms 32640 KB Output is correct
3 Correct 23 ms 32640 KB Output is correct
4 Correct 22 ms 32636 KB Output is correct
5 Incorrect 23 ms 32640 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32640 KB Output is correct
2 Correct 22 ms 32640 KB Output is correct
3 Correct 23 ms 32640 KB Output is correct
4 Correct 22 ms 32636 KB Output is correct
5 Incorrect 23 ms 32640 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -