oj.uz

답안 #683388

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683388 2023-01-18T10:08:50 Z Mkswll Pictionary (COCI18_pictionary) C++17
140 / 140
 107 ms 22704 KB 
#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

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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 596 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1332 KB Output is correct
2 Correct 36 ms 1244 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 1740 KB Output is correct
2 Correct 29 ms 1612 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 5684 KB Output is correct
2 Correct 21 ms 5588 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 7596 KB Output is correct
2 Correct 41 ms 8396 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 10924 KB Output is correct
2 Correct 36 ms 11192 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 14244 KB Output is correct
2 Correct 88 ms 16068 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 17872 KB Output is correct
2 Correct 89 ms 20080 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 22704 KB Output is correct
2 Correct 97 ms 22496 KB Output is correct