Submission #1218034

#TimeUsernameProblemLanguageResultExecution timeMemory
1218034steveonalexTeleporters (IOI08_teleporters)C++20
25 / 100
595 ms46448 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define MASK(i) (1ULL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) #define ALL(v) (v).begin(), (v).end() ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));} ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);} ll LASTBIT(ll mask){return (mask) & (-mask);} int pop_cnt(ull mask){return __builtin_popcountll(mask);} int ctz(ull mask){return __builtin_ctzll(mask);} int logOf(ull mask){return 63 - __builtin_clzll(mask);} mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);} template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b) {a = b; return true;} return false; } template <class T> void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){ for(auto item: container) out << item << separator; out << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } struct DSU{ int n; vector<int> parent, sz; DSU(int _n){ n = _n; parent.resize(n); sz.resize(n, 1); for(int i = 0; i<n; ++i) parent[i] = i; } int find_set(int u){return (u == parent[u]) ? u : (parent[u] = find_set(parent[u]));} bool same_set(int u, int v){return find_set(u) == find_set(v);} bool join_set(int u, int v){ u = find_set(u), v = find_set(v); if (u != v){ if (sz[u] < sz[v]) swap(u, v); parent[v] = u; sz[u] += sz[v]; return true; } return false; } int get_size(int u){return sz[find_set(u)];} }; const int N = 2e6 + 69; int graph[N]; void solve(){ int n, m; cin >> n >> m; vector<pair<int, int>> a(n); for(int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second; vector<int> X; for(auto i: a){ X.push_back(i.first); X.push_back(i.second); } X.push_back(0); remove_dup(X); for(auto i: a){ int l = lower_bound(ALL(X), i.first) - X.begin() - 1; int r = lower_bound(ALL(X), i.second) - X.begin(); graph[l] = r; graph[r-1] = l+1; } int t = X.size(); DSU mst(t); for(int i = 0; i < t; ++i){ mst.join_set(i, graph[i]); } int ans = mst.get_size(0) - 1; vector<int> cc; for(int i = 0; i < t; ++i) if (!mst.same_set(0, i) && mst.find_set(i) == i){ cc.push_back(mst.get_size(i)); } sort(ALL(cc)); while(m--){ if (cc.size()){ int u = cc.back(); cc.pop_back(); ans += u + 2; } else{ ans += 2; } } if (cc.size()) assert(false); cout << ans << "\n"; } int main(void){ ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); clock_t start = clock(); solve(); cerr << "Time elapsed: " << clock() - start << "ms!\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...
#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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...