Submission #537756

#TimeUsernameProblemLanguageResultExecution timeMemory
537756kabikaWalking (NOI12_walking)C++17
0 / 25
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define ti w[i].first #define vi w[i].second #define tj w[j].first #define vj w[j].second struct UFDS { vector<int> root, sz; UFDS(int n) : root(n), sz(n, 1) { iota(root.begin(), root.end(), 0); } int findRoot(int x) { return x == root[x] ? x : root[x] = findRoot(root[x]); } bool same(int x, int y) { return findRoot(x) == findRoot(y); } bool unite(int x, int y) { x = findRoot(x); y = findRoot(y); if(x == y) return 0; if(sz[x] < sz[y]) swap(x, y); sz[x] += sz[y]; root[y] = x; return 1; } int size(int x) { return sz[findRoot(x)]; } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int l, n; cin >> l >> n; vector<pair<int,int>> w(n); for(int i = 0; i < n; ++i) cin >> ti >> vi; sort(w.begin(), w.end()); UFDS ds(n); for(int i = 0; i < n; ++i) { for(int j = i + 1; j < n; ++j) { if(!ds.same(i,j)) { double m1 = (double)l/vi + ti; double m2 = (double)l/vj + tj; if(vi != vj && m2 > m1) ds.unite(i, j); } } } int frsz = 0; for(int i = 0; i < n; ++i) frsz = max(frsz, ds.size(i)); cout << frsz << '\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...