Submission #137285

#TimeUsernameProblemLanguageResultExecution timeMemory
137285choikiwonAncient Books (IOI17_books)C++17
0 / 100
42 ms31736 KiB
#include "books.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1000010; int fa[maxn], sz[maxn]; void init() { for(int i = 0; i < maxn; i++) { fa[i] = i; sz[i] = 1; } } int find(int u) { if(fa[u] == u) return u; else return fa[u] = find(fa[u]); } void mrg(int u, int v) { u = find(u); v = find(v); if(u == v) return; fa[v] = u; sz[u] += sz[v]; } int N, S; int A[maxn], vis[maxn]; vector<pii> E[maxn]; ll minimum_walk(std::vector<int> p, int s) { N = p.size(); S = s; for(int i = 0; i < N; i++) { A[i] = p[i]; } init(); ll ret = 0; for(int i = 0; i < N; i++) { if(vis[i]) continue; int mx = i; int u = i; while(!vis[u]) { vis[u] = 1; mx = max(mx, u); ret += abs(u - A[u]); mrg(u, A[u]); u = A[u]; } } int st = -1; for(int i = 0; i < N; i++) { if(i == S || sz[ find(i) ] > 1) { if(st != -1) { E[i - st].push_back(pii(st, i)); } st = i; } } for(int i = 1; i <= N; i++) { for(int j = 0; j < E[i].size(); j++) { int u = E[i][j].first; int v = E[i][j].second; if(find(u) != find(v)) { ret += 2 * i; mrg(u, v); } } } return ret; }

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:70:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < E[i].size(); j++) {
                        ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...