| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 521311 |
2022-02-01T16:30:10 Z |
ymm |
Ancient Books (IOI17_books) |
C++17 |
|
4 ms |
8140 KB |
///
/// Oh? You're approaching me?
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
#include "books.h"
const int N = 1'000'010;
int col[N]; int cnt=0;
int mn[N], mx[N];
int c1[N], c2[N];
ll minimum_walk(vector<int> p, int s) {
int n = p.size();
fill(col,col+N,-1);
fill(mn,mn+N,N);
Loop(i,0,n){
if(col[i]<0){
int j = i;
while(col[j]<0){
mn[cnt] = min(mn[cnt], j);
mx[cnt] = max(mx[cnt], j);
col[j] = cnt;
j = p[j];
}
++cnt;
}
}
int l=0, r=n-1;
while(l<s && p[l]==l) ++l;
while(r>s && p[r]==r) --r;
// Loop(i,0,n) cout << col[i] << ' '; cout << '\n';
// Loop(i,0,cnt) cout << mx[i] << ' '; cout << '\n';
// Loop(i,0,cnt) cout << mn[i] << ' '; cout << '\n';
Loop(i,l,r+1){
c1[i]++;
c1[mx[col[i]]]--;
c2[i+1]--;
c2[mn[col[i]]+1]++;
}
int root, droot;
// bfs
{
vector<int> dis(n, N);
set<int> cand; Loop(i,l,r+1) cand.insert(0);
deque<pii> q; q.emplace_back(col[s], 0); dis[col[s]]=0;
while(q.size()){
auto [v, d] = q.front(); q.pop_front();
if(d != dis[v]) continue;
int mn = ::mn[v], mx = ::mx[v];
if(mn <= s && s <= mx) { root = v; droot = d; }
for(;;){
int i;
auto it = cand.lower_bound(mn);
if(it == cand.end() || (i = *it) > mx) break;
cand.erase(it);
if(d < dis[i = col[i]]){
dis[i] = d;
q.emplace_front(i, d);
}
}
if(l<mn && d+1<dis[col[mn-1]]){
dis[col[mn-1]] = d+1;
q.emplace_back(col[mn-1], d+1);
}
if(mx<r && d+1<dis[col[mx+1]]){
dis[col[mx+1]] = d+1;
q.emplace_back(col[mn-1], d+1);
}
}
}
// cout << root << ' ' << droot << '\n';
ll ans = 0;
Loop(i,l,r+1) ans += abs(i-p[i]);
Loop(i,mx[root]+1,r+1) if(mn[col[i]] == i) ++droot;
Loop(i,l,mn[root]) if(mx[col[i]] == i) ++droot;
return ans+2*droot;
}
//int main()
//{
// cout << minimum_walk({0, 2, 3, 1}, 0) << '\n';
//}
Compilation message
books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:86:14: warning: 'droot' may be used uninitialized in this function [-Wmaybe-uninitialized]
86 | return ans+2*droot;
| ~^~~~~~
books.cpp:85:18: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
85 | Loop(i,l,mn[root]) if(mx[col[i]] == i) ++droot;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8140 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8140 KB |
3rd lines differ - on the 1st token, expected: '6', found: '8' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8140 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8140 KB |
3rd lines differ - on the 1st token, expected: '6', found: '8' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8140 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8140 KB |
3rd lines differ - on the 1st token, expected: '6', found: '8' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8140 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3314' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8140 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8140 KB |
3rd lines differ - on the 1st token, expected: '6', found: '8' |
| 3 |
Halted |
0 ms |
0 KB |
- |
