Submission #1166429

#TimeUsernameProblemLanguageResultExecution timeMemory
1166429pg_mazenPictionary (COCI18_pictionary)C++20
0 / 140
1 ms576 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; using cd = complex<double>; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; #define el '\n' #define sp ' ' #define all(v) v.begin(), v.end() #define rall(v) (v).rbegin(), (v).rend() #define YES cout << "YES\n" #define Yes cout << "Yes\n" #define yes cout << "yes\n" #define NO cout << "NO\n" #define No cout << "No\n" #define no cout << "no\n" #define int long long #define double long double #define ll long long #define ull unsigned long long #define ld long double #define pii pair<int, int> #define pll pair<ll,ll> #define loop int t; cin >> t; for(int i=1;i<=t;++i) #define mms(arr, val) memset(arr, val, sizeof arr) void PG_Mazen() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } const double EPS = 1e-7, PI = acos(-1); const int N = 1e5 + 5, MOD = 1e9 + 7, oo = 0x3f3f3f3f; const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1}; const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1}; const int knightX[] = {-2, -2, 2, 2, 1, 1, -1, -1}; const int knightY[] = {-1, 1, -1, 1, -2, 2, -2, 2}; const ll ooo = 0x3f3f3f3f3f3f3f3f; struct DSU { vector<int> par, sz; DSU(int n) { par = sz = vector<int>(n + 1); for (int i = 0; i <= n; ++i) { par[i] = i; sz[i] = 1; } } int getParent(int x) { if (par[x] == x) return x; return par[x] = getParent(par[x]); } bool connect(int u, int v) { u = getParent(u); v = getParent(v); if (u == v) return false; if (sz[u] < sz[v]) par[u] = v, sz[v] += sz[u]; else par[v] = u, sz[u] += sz[v]; return true; } bool isConnected(int u, int v) { return getParent(u) == getParent(v); } }; int ql[N], qr[N], ans[N]; void testCase() { int n, m, q; cin >> n >> m >> q; vector<pair<int, int>> que(q); for (int i = 0; i < q; ++i) { cin >> que[i].first >> que[i].second; ql[i] = 1; qr[i] = m; } bool all_answered = false; while (!all_answered) { all_answered = true; vector<vector<int>> mids(m + 1); for (int i = 0; i < q; ++i) { if (ql[i] <= qr[i]) { mids[(ql[i] + qr[i]) / 2].push_back(i); all_answered = false; } } DSU dsu(n + 1); for (int mid = 1; mid <= m; ++mid) { int cur = m - mid + 1, lst = cur; for (int j = cur * 2; j <= n; j += mid) { dsu.connect(lst, j); lst = j; } for (auto &i: mids[mid]) { int a = que[i].first, b = que[i].second; if (dsu.isConnected(a, b)) qr[i] = mid - 1, ans[i] = mid; else ql[i] = mid + 1; } } } for(int i = 0; i < q; ++i) cout << ans[i]<< el; } int32_t main() { PG_Mazen(); //sieve(); //sieveSPF(); //precompute(); testCase(); //cerr << clock() / 1000.0 << " Secs"; }

Compilation message (stderr)

pictionary.cpp: In function 'void PG_Mazen()':
pictionary.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...