Submission #123210

#TimeUsernameProblemLanguageResultExecution timeMemory
123210SirCenessAncient Books (IOI17_books)C++14
50 / 100
806 ms171096 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define inside sl<=l&&r<=sr #define outside r<sl||sr<l #define inf 1000000009 using namespace std; typedef long long ll; int n; vector<int> arr; vector<ll> numara; vector<ll> beg; vector<ll> en; vector<ll> djkdist; vector<pair<int, pair<int, int> > > edges; list<pair<int, int> > adj[1000006]; int num = 0; vector<pair<ll, ll> > minler; vector<int> dsu; int find(int node){ if (dsu[node] == node) return node; int ans = find(dsu[node]); return dsu[node] = ans; } void unionn(int node1, int node2){ node1 = find(node1); node2 = find(node2); if (node1 == node2) return; dsu[node1] = node2; } void djk(int source, int size){ priority_queue<pair<int, int> > qu; qu.push(mp(0, source)); djkdist.resize(size); for (int i = 0; i < djkdist.size(); i++) djkdist[i] = -1; while (!qu.empty()){ int node = qu.top().second; ll w = -qu.top().first; qu.pop(); if (djkdist[node] != -1) continue; djkdist[node] = w; for (list<pair<int, int> >::iterator it = adj[node].begin(); it != adj[node].end(); ++it){ if (djkdist[it -> first] != -1) continue; qu.push(mp(-w-it -> second, it -> first)); } } for (int i = 0; i < size; i++) assert(djkdist[i] != -1); } ll minimum_walk(vector<int> p, int s){ arr = p; n = p.size(); numara.resize(n); int sonn = n-1; while (p[sonn] == sonn && sonn > 0) sonn--; if (sonn == 0) return 0; int strt = 0; while (p[strt] == strt) strt++; ll ans = 0; for (int i = 0; i < n; i++) numara[i] = -1; for (int i = 0; i < n; i++){ if (numara[i] == -1 && p[i] != i){ int node = i; int lmost = node; int rmost = node; while (numara[node] == -1){ numara[node] = num; ans += abs(p[node] - node); node = p[node]; lmost = min(lmost, node); rmost = max(rmost, node); } beg.pb(lmost); en.pb(rmost); num++; } } //for (int i = 0; i < n; i++) cout << numara[i] << " "; cout << endl; int last = -1; for (int i = 0; i < n; i++){ if (numara[i] != -1){ if (last != -1){ //cout << "edge: " << numara[i] << " - " << numara[last] << " -> " << abs(last-i) << endl; adj[numara[i]].pb(mp(numara[last], abs(last-i))); adj[numara[last]].pb(mp(numara[i], abs(last-i))); } last = i; } } vector<list<int> > begs(n); vector<list<int> > ens(n); for (int i = 0; i < num; i++){ begs[beg[i]].pb(i); ens[en[i]].pb(i); } set<int> open; int flag = 1; vector<int> trumu(num); for (int i = 0; i < num; i++) trumu[i] = 0; for (int i = strt; i <= sonn; i++){ for (list<int>::iterator it = begs[i].begin(); it != begs[i].end(); ++it){ if (open.size() == 0) trumu[*it] = 1; open.insert(*it); } int foo = 0; for (list<int>::iterator it = ens[i].begin(); it != ens[i].end(); ++it){ //assert(open.find(*it) != open.end()); open.erase(open.find(*it)); if (trumu[*it] == 1) foo = 1; } if (open.size() == 0) ans += 2; if (i == s && open.size() == 0){ flag = 0; } if (foo){ for (set<int>::iterator it = open.begin(); it != open.end(); ++it){ trumu[*it] = 1; } } } ans -= 2; ll mindist = inf; for (int i = s; i < n; i++){ if (numara[i] != -1){ djk(numara[i], num); for (int j = 0; j < num; j++){ if (trumu[j] == 0) continue; mindist = min(mindist, abs(i-s) + djkdist[j]); } break; } } for (int i = s; i >= 0; i--){ if (numara[i] != -1){ djk(numara[i], num); for (int j = 0; j < num; j++){ if (trumu[j] == 0) continue; mindist = min(mindist, abs(i-s) + djkdist[j]); } break; } } if (flag) ans += 2*mindist; /*cout << "trumu: "; for (int i = 0; i < num; i++) cout << trumu[i] << " "; cout << endl; cout << "sonn: " << sonn << endl; cout << "strt: " << strt << endl; cout << "mindist: " << mindist << endl;*/ return ans; }

Compilation message (stderr)

books.cpp: In function 'void djk(int, int)':
books.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < djkdist.size(); i++) djkdist[i] = -1;
                  ~~^~~~~~~~~~~~~~~~
#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...