Submission #1012741

#TimeUsernameProblemLanguageResultExecution timeMemory
1012741ThegeekKnight16Ancient Books (IOI17_books)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; const int INF = 0x3f3f3f3f; #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,tune=native") vector<vector<pair<int, int>>> adj; int create() { adj.emplace_back(); return adj.size()-1; } int build(int ini, int fim) { if (ini == fim) { return ini; } int pos = create(); int m = (ini + fim) >> 1; adj[pos].emplace_back(build(ini, m), 0); adj[pos].emplace_back(build(m+1, fim), 0); return pos; } void update(int pos, int ini, int fim, int p, int q, int val) { if (q < ini || p > fim) return; if (p <= ini && fim <= q) {adj[val].emplace_back(pos, 0); return;} int m = (ini + fim) >> 1; int e = adj[pos][0].first, d = adj[pos][1].first; update(e, ini, m, p, q, val); update(d, m+1, fim, p, q, val); } queue<int> fila[2]; void add( int node, int d ){ fila[d%2].push(node); dist[node] = d; } void bfs( int source ){ int a = 0, b = 1; add( source, 0 ); while( !fila[a].empty() ){ int cur = fila[a].front(); fila[a].pop(); if( marc[cur] ) continue; marc[cur] = true; for( auto [viz, p] : adj[cur] ) if( dist[viz] > dist[cur] + p ) add( viz, dist[cur] + p ); if( fila[a].empty() ) swap( a, b ); } } long long minimum_walk(std::vector<int> p, int s) { int N = p.size(); long long resp = 0; for (int i = 0; i < N; i++) resp += abs(p[i]-i); if (resp == 0) return 0; vector<int> minSuf(N); minSuf.back() = p.back(); for (int i = N-2; i >= 0; i--) minSuf[i] = min(minSuf[i+1], p[i]); vector<int> maxPref(N); maxPref[0] = p[0]; for (int i = 1; i < N; i++) maxPref[i] = max(maxPref[i-1], p[i]); int lastS = 0; vector<pair<int, int>> comps; for (int i = 1; i < N; i++) if (maxPref[i-1] < i && minSuf[i] >= i) { comps.emplace_back(lastS, i-1); // resp += i - lastS; lastS = i; } comps.emplace_back(lastS, N-1); while (!comps.empty() && comps.back().first == comps.back().second) comps.pop_back(); reverse(comps.begin(), comps.end()); while (!comps.empty() && comps.back().first == comps.back().second) comps.pop_back(); reverse(comps.begin(), comps.end()); for (int i = 0; i+1 < comps.size(); i++) resp += 2*(comps[i+1].first - comps[i].second); if (s < comps[0].first) resp += 2*(comps[0].first - s); else if (s > comps.back().second) resp += 2*(s - comps.back().second); else { //Parte ruim adj.resize(N); int root = build(0, N-1); for (int i = 0; i < N; i++) { int l = min(i, p[i]), r = max(i, p[i]); update(root, 0, N-1, l, r, i); if (l > 0) adj[i].emplace_back(l-1, +1); if (r+1 < N) adj[i].emplace_back(r+1, +1); } queue<int> q1, q2; vector<int> Marc(adj.size()), Dist(adj.size(), INF); q1.push(s); Dist[s] = 0; while (!q1.empty() || !q2.empty()) { int cur; if (!q1.empty()) cur = q1.front(), q1.pop(); else cur = q2.front(), q2.pop(); if (Marc[cur]) continue; Marc[cur] = 1; for (auto [viz, p] : adj[cur]) { if (Marc[viz]) continue; if (Dist[viz] <= Dist[cur] + p) continue; if (p == 0) q1.push(viz); else q2.push(viz); Dist[viz] = Dist[cur]+p; } } for (auto [x, y] : comps) { if (x <= s && s <= y) { resp += 2*Dist[x]; break; } } } return resp; }

Compilation message (stderr)

books.cpp: In function 'void add(int, int)':
books.cpp:42:2: error: 'dist' was not declared in this scope
   42 |  dist[node] = d;
      |  ^~~~
books.cpp: In function 'void bfs(int)':
books.cpp:51:7: error: 'marc' was not declared in this scope
   51 |   if( marc[cur] ) continue; marc[cur] = true;
      |       ^~~~
books.cpp:51:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   51 |   if( marc[cur] ) continue; marc[cur] = true;
      |   ^~
books.cpp:51:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   51 |   if( marc[cur] ) continue; marc[cur] = true;
      |                             ^~~~
books.cpp:51:29: error: 'marc' was not declared in this scope
books.cpp:52:39: error: 'dist' was not declared in this scope
   52 |   for( auto [viz, p] : adj[cur] ) if( dist[viz] > dist[cur] + p ) add( viz, dist[cur] + p );
      |                                       ^~~~
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:78:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i+1 < comps.size(); i++) resp += 2*(comps[i+1].first - comps[i].second);
      |                     ~~~~^~~~~~~~~~~~~~