Submission #1060603

#TimeUsernameProblemLanguageResultExecution timeMemory
1060603ewirlanHighway Tolls (IOI18_highway)C++17
69 / 100
155 ms12000 KiB
// #ifndef __SIZEOF_INT128__ #define __SIZEOF_INT128__ #endif #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include "highway.h" using namespace std; using namespace chrono; using namespace __gnu_pbds; template <typename T> using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; #define rep(i, p, k) for(int i(p); i < (k); ++i) #define per(i, p, k) for(int i(p); i > (k); --i) #define sz(x) (int)(x).size() #define sc static_cast typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef __int128_t lll; //#define int ll template <typename T = int> using par = std::pair <T, T>; #define fi first #define se second #define test int _number_of_tests(in()); while(_number_of_tests--) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define pb emplace_back struct Timer { string name{""}; time_point<high_resolution_clock> end, start{high_resolution_clock::now()}; duration<float, std::milli> dur; Timer() = default; Timer(string nm): name(nm) {} ~Timer() { end = high_resolution_clock::now(); dur= end - start; cout << "@" << name << "> " << dur.count() << " ms" << '\n'; } }; template <typename T = int> inline T in() { static T x; std::cin >> x; return x; } std::string yn(bool b) { if(b) return "YES\n"; else return "NO\n"; } template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par); template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek) { for(const auto& i : wek)out << i << ' '; return out; } template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par) { out << '{'<<par.first<<", "<<par.second<<"}"; return out; } #define show(x) cerr << #x << " = " << x << '\n'; constexpr int maxn = 90003; vector <pair<int, int>> graf[maxn]; int odl[maxn]; bool xd[maxn]; void dfs(int w, bool x) { odl[w] = 1; xd[w] = x; for(auto [i, j]: graf[w])if(!odl[i])dfs(i, !x); } void find_pair(int n, vector <int> ka, vector <int> kb, int a, int b) { int m(sz(ka)); rep(i, 0, m){ graf[ka[i]].pb(kb[i], i); graf[kb[i]].pb(ka[i], i); } dfs(1, 0); vector <int> xdd[2]; rep(i, 0, n)xdd[xd[i]].pb(i); vector vv = xdd[sz(xdd[1]) < sz(xdd[0])]; ll d(ask(vector<int>(m, 0))/a); auto pyt = [n,m](vector <bool> v){ vector <int> w(m); rep(i, 0, n)if(v[i])for(auto [i, j]: graf[i])w[j] |= 1; return ask(w); }; int p(0), k(sz(vv)), s; vector <bool> v(n); while(k > p){ s = (p+k)/2; rep(i, 0, n)v[i] = 0; rep(i, 0, sz(vv))v[vv[i]] = i >= s; if(pyt(v) == d*a)k = s; else p = s+1; } int r(p-1); vector <int> so; queue <int> kul; bool je(0); rp: rep(i, 0, n)odl[i] = 0; so = {r}; kul.push(r); odl[r] = 1; while(kul.size()){ auto t(kul.front()); kul.pop(); for(auto [i, j]: graf[t])if(!odl[i]){ kul.push(i); so.pb(i); odl[i] = odl[t]+1; } } if(je){ vector <int> s; for(auto i: so)if(odl[i] == d+1)s.pb(i); so = s; } p = 0, k = sz(so); while(k > p){ s = (p+k)/2; rep(i, 0, n)v[i] = 0; rep(i, 0, sz(so))v[so[i]] = i >= s; if(pyt(v) == d*a)k = s; else p = s+1; } if(!je){ r = so[p-1]; je = 1; goto rp; } answer(r, so[p-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...
#Verdict Execution timeMemoryGrader output
Fetching results...