Submission #347767

#TimeUsernameProblemLanguageResultExecution timeMemory
347767BorisBarcaPictionary (COCI18_pictionary)C++14
140 / 140
163 ms7172 KiB
/* $$$$$$$\ $$\ $$$$$$$\ $$ __$$\ \__| $$ __$$\ $$ | $$ | $$$$$$\ $$$$$$\ $$\ $$$$$$$\ $$ | $$ | $$$$$$\ $$$$$$\ $$$$$$$\ $$$$$$\ $$$$$$$\ |$$ __$$\ $$ __$$\ $$ |$$ _____|$$$$$$$\ | \____$$\ $$ __$$\ $$ _____|\____$$\ $$ __$$\ $$ / $$ |$$ | \__|$$ |\$$$$$$\ $$ __$$\ $$$$$$$ |$$ | \__|$$ / $$$$$$$ | $$ | $$ |$$ | $$ |$$ | $$ | \____$$\ $$ | $$ |$$ __$$ |$$ | $$ | $$ __$$ | $$$$$$$ |\$$$$$$ |$$ | $$ |$$$$$$$ |$$$$$$$ |\$$$$$$$ |$$ | \$$$$$$$\\$$$$$$$ | \_______/ \______/ \__| \__|\_______/ \_______/ \_______|\__| \_______|\_______| */ #include <bits/stdc++.h> #include <ext/pb_ds/detail/standard_policies.hpp> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define PB push_back #define MP make_pair #define INS insert #define LB lower_bound #define UB upper_bound #define pii pair <int,int> #define pll pair <long long, long long> #define X first #define Y second #define _ << " " << #define sz(x) (int)x.size() #define all(a) (a).begin(),(a).end() #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define FORD(i, a, b) for (int i = (a); i > (b); --i) #define FORA(i, x) for (auto &i : x) #define REP(i, n) FOR(i, 0, n) #define BITS(x) __builtin_popcount(x) #define SQ(a) (a) * (a) #define TRACE(x) cout << #x " = " << (x) << '\n'; #define YES cout << "YES\n" #define NO cout << "NO\n" #define umap unordered_map typedef long long ll; typedef long double ld; typedef vector <int> vi; typedef vector <pii> vpi; typedef vector <ll> vll; typedef vector <pll> vpl; typedef vector <double> vd; typedef vector <ld> vld; typedef vector<string> vs; typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set; //find_by_order -> kti najmanji //order_of_key -> koliko ima manjih od x //((float) t)/CLOCKS_PER_SEC const int MOD = 1e9 + 7; const double PI = acos(-1); const int INF = 1e9 + 10; const ll INFL = 1e18 + 10; const int ABC = 30; const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; const int dox[] = {-1, 1, 0, 0, -1, -1, 1, 1}; const int doy[] = {0, 0, -1, 1, -1, 1, -1, 1}; inline int sum(int a, int b){ if (a + b < 0) return (a + b + MOD) % MOD; return (a + b) % MOD; } inline void add(int &a, int b){ a = sum(a, b); } inline int mul(ll a, ll b){ return ((a % MOD) * ((ll)b % MOD)) % MOD; } inline int sub(int a, int b){ return (a - b + MOD) % MOD; } inline int fast_pot(ll pot, ll n){ ll ret = 1; while (n){ if (n & 1LL) ret = (ret * pot) % MOD; pot = (pot * pot) % MOD; n >>= 1LL; } return ret; } inline int divide(int a, int b){ return mul(a, fast_pot(b, MOD - 2)); } ll lcm(ll a, ll b){ return abs(a * b) / __gcd(a, b); } inline double ccw(pii A, pii B, pii C){ return (A.X * B.Y) - (A.Y * B.X) + (B.X * C.Y) - (B.Y * C.X) + (C.X * A.Y) - (C.Y * A.X); } inline int CCW(pii A, pii B, pii C){ double val = ccw(A, B, C); double eps = max(max(abs(A.X), abs(A.Y)), max(max(abs(B.X), abs(B.Y)), max(abs(C.X), abs(C.Y)))) / 1e9; if (val <= -eps) return -1; if (val >= eps) return 1; return 0; } void to_upper(string &x){ REP(i, sz(x)) x[i] = toupper(x[i]); } void to_lower(string &x){ REP(i, sz(x)) x[i] = tolower(x[i]); } string its(ll x){ if (x == 0) return "0"; string ret = ""; while (x > 0){ ret += (x % 10) + '0'; x /= 10; } reverse(all(ret)); return ret; } ll sti(string s){ ll ret = 0; REP(i, sz(s)){ ret *= 10; ret += (s[i] - '0'); } return ret; } const int N = 1e5 + 10; int n, m, q, p[N], sz[N], sol[N]; stack <pii> s; vpi edg[N], Q; int find(int node){ if (p[node] == node) return node; return find(p[node]); } void merge(int x, int y){ x = find(x); y = find(y); if (x == y) return; if (sz[x] < sz[y]) swap(x, y); s.push({y, p[y]}); sz[x] += sz[y]; p[y] = x; } void rollback(int x){ while (sz(s) > x){ int x = s.top().X; int y = s.top().Y; s.pop(); sz[p[x]] -= sz[x]; p[x] = y; } } void solve(int lo, int hi, vi &v){ if (sz(v) == 0) return; if (lo == hi - 1){ FORA(x, v) sol[x] = min(sol[x], lo); return; } int prije = sz(s); int mid = (lo + hi) / 2; for (int i = lo; i < mid; ++i){ int x = m - i + 1; for (int j = 2 * x; j <= n; j += x) merge(x, j); } vi l, r; FORA(x, v){ if (find(Q[x].X) == find(Q[x].Y)) l.PB(x); else r.PB(x); } v.clear(); v.shrink_to_fit(); solve(mid, hi, r); rollback(prije); solve(lo, mid, l); } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(NULL)); cin >> n >> m >> q; // FOR(i, 1, m + 1){ // for (int j = 2 * i; j <= n; j += i){ // //cout << m - i _ i _ j << '\n'; // edg[m - i + 1].PB({i, j}); // } // } REP(i, n + 1){ p[i] = i; sz[i] = 1; } vi v; REP(i, q){ int a, b; cin >> a >> b; Q.PB({a, b}); v.PB(i); sol[i] = INF; } solve(1, m + 1, v); REP(i, q) cout << sol[i] << '\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...