Submission #441994

#TimeUsernameProblemLanguageResultExecution timeMemory
441994SorahISAFountain Parks (IOI21_parks)C++17
45 / 100
944 ms58008 KiB
#include "parks.h" #pragma GCC optimize("Ofast", "unroll-loops") #include <bits/stdc++.h> using namespace std; // #define int long long // #define double long double using pii = pair<int, int>; template<typename T> using Prior = std::priority_queue<T>; template<typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>; // #define X first // #define Y second #define eb emplace_back #define pb pop_back #define pf pop_front #define ALL(x) begin(x), end(x) #define RALL(x) rbegin(x), rend(x) namespace { mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 2E5 + 5; const int dx[] = {2, 0, -2, 0}; const int dy[] = {0, 2, 0, -2}; map<pii, int> fountain; vector<int> p(maxn); vector<int> adj[maxn]; int R(int x) {return x ^ p[x] ? p[x] = R(p[x]) : x;} int U(int x, int y) {x = R(x), y = R(y); return x ^ y ? p[x] = y, 1 : 0;} } /// end of namespace int construct_roads(vector<int> X, vector<int> Y) { int N = X.size(); vector<int> u, v, a, b; if (N == 1) return build({}, {}, {}, {}), 1; iota(ALL(p), 0); for (int i = 0; i < N; ++i) fountain[{X[i], Y[i]}] = i+1; for (int i = 0; i < N; ++i) { for (int d = 0; d < 4; ++d) { int nei = fountain[{X[i] + dx[d], Y[i] + dy[d]}]; if (nei-1 > i and U(i, nei-1)) u.eb(i), v.eb(nei-1); } } for (int i = 0; i < N; ++i) if (R(i) != R(0)) return 0; int M = u.size(); a.assign(M, -1), b.assign(M, -1); // assert(M == N-1); for (int i = 0; i < M; ++i) { if (X[u[i]] == X[v[i]]) { int midY = Y[u[i]] + Y[v[i]] >> 1; if ((X[u[i]] + 1 + midY) % 4 == 2) a[i] = X[u[i]] + 1; else a[i] = X[u[i]] - 1; b[i] = midY; } } for (int i = 0; i < M; ++i) { if (Y[u[i]] == Y[v[i]]) { int midX = X[u[i]] + X[v[i]] >> 1; if ((Y[u[i]] + 1 + midX) % 4 == 0) b[i] = Y[u[i]] + 1; else b[i] = Y[u[i]] - 1; a[i] = midX; } } return build(u, v, a, b), 1; }

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:61:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |             int midY = Y[u[i]] + Y[v[i]] >> 1;
parks.cpp:70:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |             int midX = X[u[i]] + X[v[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...
#Verdict Execution timeMemoryGrader output
Fetching results...