Submission #683388

#	Time	Username	Problem	Language	Result	Execution time	Memory
683388		Mkswll	Pictionary (COCI18_pictionary)	C++17	140 / 140	107 ms	22704 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;
typedef pair <int, ll> pil;
typedef pair <ll, ll> pll;
typedef pair <ld, ld> pdd;
#define cio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define cases int _; cin >> _; while(_--)
#define pb push_back
#define eb emplace_back
#define space << " " <<
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Unique(v) v.erase(unique(all(v)), v.end())
#define mset(x) memset(x, 0, sizeof(x))
#define sflush fflush(stdout)
#define cflush cout.flush()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define nl cout << "\n";
#define binary(len, num) bitset <len> (num)
#define vt vector
#define ar array
#define Mat vt <vt <int> >

template <typename T> istream& operator >> (istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template <typename T> ostream& operator << (ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};

int read(){
    int w = 1, c, ret;
    while((c = getchar()) > '9' || c < '0'){
        w = (c == '-' ? -1 : 1);
    }
    ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9'){
        ret = ret * 10 + c - '0';
    }
    return ret * w;
}

int rd(){
	int in;
	cin >> in;
	return in;
}
 
void write(int x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9){
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

const int MAXN = 1e5 + 5, MAXM = 2e5 + 5, INF = 1e9 + 5, MOD = 1e9 + 7;
const ll LINF = 1e18 + 5;
const ld ep = 1e-8, Pi = acos(-1.0);

int n, m, k, x, q; 
int a[MAXN];
string s;

int fa[MAXN], rk[MAXN], siz[MAXN];

int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y){
	int fx = find(x), fy = find(y);
	if(fx == fy){
		return;
	}
	if(rk[fx] > rk[fy]) swap(fx, fy);
	fa[fx] = fy;
	siz[fy] += siz[fx];
	if(rk[fx] == rk[fy]) ++rk[fy];
}

struct edge{
	int f, t, val, next;
} e[MAXM];

int head[MAXN], te = 0;
int dep[MAXN];

void add_edge(int u, int v, int w){
	e[++te].f = u;
	e[te].t = v;
	e[te].next = head[u];
	e[te].val = w;
	head[u] = te;
}

int p[MAXN][20], mx[MAXN][20];

void dfs(int cur){
	dep[cur] = dep[p[cur][0]] + 1;
	// cout << cur << " " << dep[cur] space dep[p[cur][0]] << "\n";
	for(int i = head[cur]; i; i = e[i].next){
		int to = e[i].t;
		if(to == p[cur][0]) continue;
		p[to][0] = cur;
		mx[to][0] = e[i].val;
		dfs(to);
	}
}


int calc(int u, int v){
	int ret = 0;
	// cout << dep[u] space dep[v] << " ";
	if(dep[u] < dep[v]) swap(u, v);
	bool flag = (u == 8);
	if(dep[u] > dep[v]){
		int dif = dep[u] - dep[v];
		for(int i = 0; i <= 20; ++i){
			if((1 << i) & dif){
				ret = max(ret, mx[u][i]);
				u = p[u][i];
			}
		}
	}
	// cout << u space v << "\n";
	if(u == v) return ret;
	
	for(int i = 19; i >= 0; --i){
		if(p[u][i] != p[v][i]){
			ret = max({ret, mx[u][i], mx[v][i]});
			u = p[u][i];
			v = p[v][i];
			// cout << ret space u space v space i << "\n";
		}
	}
	if(u != v){
		ret = max({ret, mx[u][0], mx[v][0]});
	}
	return ret;
}

void clear(){
    
}

int main(){
    cio;
    cin >> n >> m >> q;
    iota(fa + 1, fa + n + 1, 1);
    generate(rk + 1, rk + n + 1, []{ return 1; });
    
    
    for(int i = m; i >= 1; --i){
    	for(int j = i; ; j += i){
    		if(j + i > n) break;
    		if(find(j) == find(j + i)) continue;
    		merge(j, j + i);
    		add_edge(j, j + i, m - i + 1);
    		add_edge(j + i, j, m - i + 1);
    		// cout << j space j + i space m - i + 1 << "\n";
    	}
    }
    
    dfs(1);
    
    int up = log2(n);
    
    for(int i = 1; i <= up; ++i){
    	for(int j = 1; j <= n; ++j){
    		
    		p[j][i] = p[p[j][i - 1]][i - 1];
    		mx[j][i] = max(mx[j][i - 1], mx[p[j][i - 1]][i - 1]);
    		// cout << p[j][i] << " ";
    	}
    	// nl;
    }
    
    for(int i = 1; i <= n; ++i){
    	// cout << i space p[i][0] << "\n";
    }
    
    for(int i = 1; i <= q; ++i){
    	int u = rd(), v = rd();
    	cout << calc(u, v) << "\n";
    }
    
    return 0;
}   

Compilation message (stderr)

pictionary.cpp: In function 'int calc(int, int)':
pictionary.cpp:126:7: warning: unused variable 'flag' [-Wunused-variable]
  126 |  bool flag = (u == 8);
      |       ^~~~

• 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