Submission #40004

#TimeUsernameProblemLanguageResultExecution timeMemory
40004krauchČVENK (COI15_cvenk)C++14
0 / 100
537 ms524288 KiB
/* _ _ _______ _ _ | | / / | _____| | | / / | | / / | | | | / / | |/ / | |_____ | |/ / | |\ \ | _____| | |\ \ | | \ \ | | | | \ \ | | \ \ | |_____ | | \ \ |_| \_\ |_______| |_| \_\ */ #include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; typedef double ld; typedef pair <int, int> PII; typedef pair <ll, ll> PLL; typedef pair < ll, int > PLI; #define F first #define S second #define pb push_back #define eb emplace_back #define right(x) x << 1 | 1 #define left(x) x << 1 #define forn(x, a, b) for (int x = a; x <= b; ++x) #define for1(x, a, b) for (int x = a; x >= b; --x) #define mkp make_pair #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define y1 kekekek #define fname "" const ll ool = 1e18 + 9; const int oo = 1e9 + 9, base = 1e9 + 7; const ld eps = 1e-7; const int N = 1e5 + 6; bool cmp(pair < PII, int > a, pair < PII, int > b) { if (a.F.S != b.F.S) return a.F.S < b.F.S; return a.F.F < b.F.F; } int n; vector < PII > vec; vector < pair < PII, int > > a; ll d[N], sz[N], ans = ool; vector < pair < int, ll > > g[N]; map < PII, int > cnt; void calc(int v, int par) { for (auto it : g[v]) { int to = it.F; if (to == par) continue; //cerr << vec[v - 1].F << " " << vec[v - 1].S << " --" << it.S << "--> " << vec[to - 1].F << " " << vec[to - 1].S << "\n"; calc(to, v); sz[v] += sz[to]; d[v] += d[to] + sz[to]; } } void dfs(int v, int par, ll up) { for (auto it : g[v]) { int to = it.F; if (to == par) continue; ans = min(ans, up + d[to] + min(sz[to], sz(a) - sz[to]) * it.S); dfs(to, v, up + d[v] - d[to] - sz[to] + (sz(a) - sz[to]) * it.S); } } int main() { #ifdef krauch freopen("input.txt", "r", stdin); #else //freopen(fname".in", "r", stdin); //freopen(fname".out", "w", stdout); #endif cin >> n; forn(i, 1, n) { int x, y; cin >> x >> y; cnt[PII(x, y)]++; vec.eb(x, y); forn(i, 0, 31) { if (!((x >> i) & 1) && !(y >> i) & 1) continue; if ((x >> i) & 1) x -= 1 << i; if ((y >> i) & 1) y -= 1 << i; vec.eb(x, y); assert(sz(vec) <= (int)1e7); } } sort(all(vec)); vec.erase(unique(all(vec)), vec.end()); forn(i, 0, sz(vec) - 1) { a.eb(vec[i], i + 1); sz[i + 1] = cnt[PII(vec[i].F, vec[i].S)]; if (i && vec[i - 1].F == vec[i].F) { g[i].eb(i + 1, vec[i].S - vec[i - 1].S); g[i + 1].eb(i, vec[i].S - vec[i - 1].S); } } sort(all(a), cmp); forn(i, 1, sz(a) - 1) { if (a[i - 1].F.S == a[i].F.S) { g[a[i - 1].S].eb(a[i].S, a[i].F.F - a[i - 1].F.F); g[a[i].S].eb(a[i - 1].S, a[i].F.F - a[i - 1].F.F); } } calc(1, 0); ans = d[1]; dfs(1, 0, 0); cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...