Submission #1290736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290736		tin.le22	Pictionary (COCI18_pictionary)	C++20	140 / 140	162 ms	34840 KiB

pictionary

#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;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define vt vector
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define ub upper_bound
#define lb lower_bound
#define db double
#define ld long db
#define ll long long
#define ull unsigned long long
#define vi vt<int>
#define vvi vt<vi>
#define vvvi vt<vvi>
#define pii pair<int, int>
#define vpii vt<pii>
#define vvpii vt<vpii>
#define vll vt<ll>  
#define vvll vt<vll>
#define pll pair<ll, ll>    
#define vpll vt<pll>
#define vvpll vt<vpll>
#define ar(x) array<int, x>
#define var(x) vt<ar(x)>
#define vvar(x) vt<var(x)>
#define al(x) array<ll, x>
#define vall(x) vt<al(x)>
#define vvall(x) vt<vall(x)>
#define vs vt<string>
#define pb push_back
#define ff first
#define ss second
#define rsz resize
#define sum(x) (ll)accumulate(all(x), 0LL)
#define srt(x) sort(all(x))
#define srtR(x) sort(allr(x))
#define srtU(x) sort(all(x)), (x).erase(unique(all(x)), (x).end())
#define rev(x) reverse(all(x))
#define MAX(a) *max_element(all(a)) 
#define MIN(a) *min_element(all(a))
#define SORTED(x) is_sorted(all(x))
#define ROTATE(a, p) rotate(begin(a), begin(a) + p, end(a))
#define i128 __int128
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#if defined(LOCAL) && __has_include("debug.h")
  #include "debug.h"
#else
  #define debug(...)
  #define startClock
  #define endClock
  inline void printMemoryUsage() {}
#endif
template<class T> using max_heap = priority_queue<T>; template<class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T, size_t N> istream& operator>>(istream& is, array<T, N>& arr) { for (size_t i = 0; i < N; i++) { is >> arr[i]; } return is; }
template<typename T, size_t N> istream& operator>>(istream& is, vector<array<T, N>>& vec) { for (auto &arr : vec) { is >> arr; } return is; }
template<typename T1, typename T2>  istream &operator>>(istream& in, pair<T1, T2>& input) { return in >> input.ff >> input.ss; }
template<typename T> istream &operator>>(istream &in, vector<T> &v) { for (auto &el : v) in >> el; return in; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const static ll INF = 4e18 + 10;
const static int inf = 1e9 + 100;
const static int MX = 1e5 + 5;

struct Persistent_DSU {
	int n, version;
	vvpii parent, rank, col;
	vpii bip;
	Persistent_DSU(int n) {
		this->n = n; version = 0;
		parent.rsz(n); rank.rsz(n); col.rsz(n);
		for (int i = 0; i < n; i++) {
			parent[i].pb({version, i});
			rank[i].pb({version, 1});
			col[i].pb({version, 0});
		}
        bip.pb({version, 1});
	}
 
	int find(int u, int ver) {
		auto pr = *(ub(all(parent[u]), make_pair(ver + 1, -1)) - 1);
		return pr.ss != u ? find(pr.ss, ver) : u;
	}
 
	int get_color(int u, int ver) {
		auto cp = *(ub(all(col[u]), make_pair(ver + 1, -1)) - 1);
		int c = cp.ss;
		int pu = find(u, ver);
		return pu == u ? c : c ^ get_color(pu, ver);
	}
 
	int get_rank(int u, int ver) {
		u = find(u, ver);
		auto it = *(ub(all(rank[u]), make_pair(ver + 1, -1)) - 1);
		return it.ss;
	}

	int merge(int u, int v, int ver) {
		u = find(u, ver), v = find(v, ver);
		int cu = get_color(u, ver), cv = get_color(v, ver);
		if(u == v) {
			if((cu ^ cv) != 1) {
				version = ver;
                bip.pb({version, 0});
			}
			return 0;
		}
		version = ver;
		int szu = rank[u].back().ss;
		int szv = rank[v].back().ss;
		if(szu < szv) swap(u, v);
		parent[v].pb({version, u});
		int new_sz = szu + szv;
		rank[u].pb({version, new_sz});
		int new_col = get_color(u, ver) ^ get_color(v, ver) ^ 1;
		col[v].pb({version, new_col});
		bip.pb({version, bip.back().ss});
		return version;
	}
 
	bool same(int u, int v, int ver) {
		return find(u, ver) == find(v, ver);
	}
 
	int get_bip(int ver) {
		auto it = ub(all(bip), make_pair(ver + 1, -1)) - 1;
		return it->ss;
	}

    int earliest_time(int u, int v, int m) {
        int left = 0, right = m, res = -1;
        while(left <= right) {
            int middle = (left + right) >> 1;
            if(same(u, v, middle)) res = middle, right = middle - 1;
            else left = middle + 1;
        }
        return res;
    }
};

void solve() {
    int N, M, Q; cin >> N >> M >> Q;
    Persistent_DSU root(N + 1);
    for(int i = M; i >= 1; i--) {
        int day = M - i + 1;
        for(int j = i; j <= N; j += i) {
            root.merge(i, j, day);
        }
    }
    while(Q--) {
        int u, v; cin >> u >> v;
        cout << root.earliest_time(u, v, M) << '\n';
    }
}

signed main() {
    IOS;
    startClock
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) {   
        //cout << "Case #" << i << ": ";  
        solve();
    }
    endClock;
    printMemoryUsage();
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14