제출 #637010

#제출 시각아이디문제언어결과실행 시간메모리
637010nguyen31hoang08minh2003Sirni (COCI17_sirni)C++14
140 / 140
1427 ms638396 KiB
/* /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ \\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// =\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/= \==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/ \\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\ \\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ /==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\ =/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\= //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ \\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// =\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/= \==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/ \\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\// \\ \\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // \\ // //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ /==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\ =/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\==/\= //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ \\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// =\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/==\/= */ #include <bits/stdc++.h> #define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i) #define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i) #define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i) #define fi first #define se second #define pb push_back #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; using ll = long long; using ld = long double; template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;}; template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;}; typedef unsigned long long ull; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; struct DisjointSet { private: mutable std::vector<int> r; public: DisjointSet() {}; DisjointSet(const int n): r(n, -1) {}; void reload() { std::fill(r.begin(), r.end(), -1); }; int getRoot(const int x) const { return r[x] < 0 ? x : (r[x] = getRoot(r[x])); } bool unite(int x, int y) { x = getRoot(x); y = getRoot(y); if (x == y) return false; if (r[x] > r[y]) std::swap(x, y); r[x] += r[y]; r[y] = x; return true; } bool checkConnected(const int x, const int y) const { return getRoot(x) == getRoot(y); } int getTreeSize(const int x) const { return -r[getRoot(x)]; } }; const int maxN = 1e5 + 5, maxP = 1e7 + 7, inf = 0x3f3f3f3f, ninf = 0xc0c0c0c0; int n, mxp, p[maxN], k[maxP]; DisjointSet dsu(maxP); vii e[maxP]; void input() { cin >> n; fort(i, 1, n) { cin >> p[i]; k[p[i]] = p[i]; maxi(mxp, p[i]); } } void subtask1() { /** Prim algorithm min(x % y, y % x) = max(x, y) % min(x, y) **/ const int N = n + 5; int x; ll res = 0; vi d(N, inf); vector<bool> vis(N); d[1] = 0; fort(_, 1, n) { x = -1; fort(i, 1, n) { if (vis[i]) continue; if (x < 0 || d[x] > d[i]) x = i; } vis[x] = true; res += d[x]; fort(i, 1, n) { if (vis[i]) continue; mini(d[i], min(p[x] % p[i], p[i] % p[x])); } } cout << res << '\n'; } void subtask3() { ll res = 0; for (int i = mxp - 1, j; i >= 1; --i) if (!k[i]) k[i] = k[i + 1]; else { j = i << 1; if (i < mxp) { // for case i only add edge from i to a vertex with value in [i + 1, i * 2 - 1] if (j > mxp || k[i + 1] != k[j]) // check if there is a vertex with value in [i + 1, j - 1] e[k[i + 1] - i].emplace_back(i, k[i + 1]); } for (; j <= mxp; j += i) // for case j = i * t (i >= 2), add edge from j to a vertex with value in [j, j + i - 1] if (j + i > mxp || k[j] != k[j + i]) // check if there is a vertex with value in [j, j + i - 1] e[k[j] - j].emplace_back(i, k[j]); } fort(w, 0, mxp) for (const auto &[x, y] : e[w]) if (dsu.unite(x, y)) res += w; cout << res << '\n'; } int main() { #ifdef LOCAL freopen("input.INP", "r", stdin); #endif // LOCAL cin.tie(0) -> sync_with_stdio(0); cout.tie(0); input(); if (n <= 7500) subtask1(); else subtask3(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sirni.cpp: In function 'void subtask3()':
sirni.cpp:155:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |         for (const auto &[x, y] : e[w])
      |                          ^
#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...