oj.uz

답안 #57188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57188 2018-07-14T08:52:57 Z polyfish Pictionary (COCI18_pictionary) C++14
0 / 140
 193 ms 31564 KB 
//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 100002;
const int LG_N = 19;
const int INF = 1e9;

class disjoint_set {
public:
	int lab[MAX_N];

	disjoint_set() {
		memset(lab, 0, sizeof(lab));
	}

	int findset(int u) {
		return lab[u]<=0 ? u : lab[u] = findset(lab[u]);
	}

	bool uni(int s, int t) {
		s = findset(s);
		t = findset(t);
		if (s==t)
			return false;
		if (lab[s]<lab[t])
			lab[t] = s;
		else if (lab[s]>lab[t])
			lab[s] = t;
		else {
			lab[s] = t;
			--lab[t];
		}
	}
};

struct edge {
	int u, v, w;

	edge() {}
	edge(int u, int v, int w): 
		u(u), v(v), w(w) {}

	bool operator<(const edge &E) {
		return w > E.w;
	}
};

int n, m, nQuery, p[LG_N+2][MAX_N], min_edge[LG_N+2][MAX_N], l[MAX_N];
vector<edge> e;
vector<pair<int, int> > g[MAX_N];
disjoint_set dsu;

void sieve() {
	for (int i=1; i<=m; ++i) {
		for (int j=2*i; j<=n; j += i)
			e.push_back(edge(i, j, i));
	}
}

void process_edge(edge e) {
	if (dsu.uni(e.u, e.v)) {
		g[e.u].push_back(make_pair(e.v, e.w));
		g[e.v].push_back(make_pair(e.u, e.w));
	}
}

void build_MST() {
	sort(e.begin(), e.end());
	// for (int i=0; i<e.size(); ++i)
	// 	cerr << e[i].u << ' ' << e[i].v << ' ' << e[i].w << '\n';
	for (int i=0; i<e.size(); ++i)
		process_edge(e[i]);
}

void fix_root(int u) {
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i].first, w = g[u][i].second;
		if (v!=p[0][u]) {
			p[0][v] = u;
			min_edge[0][v] = w;
			l[v] = l[u] + 1;
			fix_root(v);
		}
	}
}

void init_lca() {
	for (int i=1; i<=LG_N; ++i) {
		for (int j=1; j<=n; ++j) {
			p[i][j] = p[i-1][p[i-1][j]];
			min_edge[i][j] = min(min_edge[i-1][j], min_edge[i-1][p[i-1][j]]);
		}
	}
}

int get_min(int x, int y) {
	int res = INF;
	for (int k=LG_N; k>=0; --k) {
		if (l[p[k][x]]>=l[y]) {
			res = min(res, min_edge[k][x]);
			x = p[k][x];
		}
	}
	for (int k=LG_N; k>=0; --k) {
		if (l[p[k][y]]>=l[x]) {
			res = min(res, min_edge[k][y]);
			y = p[k][y];
		}
	}
	for (int k=LG_N; k>=0; --k) {
		if (p[k][x]!=p[k][y]) {
			res = min(res, min(min_edge[k][x], min_edge[k][y]));
			x = p[k][x];
			y = p[k][y];
		}
	}
	while (x!=y) {
		res = min(res, min(min_edge[0][x], min_edge[0][y]));
		x = p[0][x];
		y = p[0][y];
	}
	return res;
}

void solve_query() {
	while (nQuery--) {
		int u, v;
		cin >> u >> v;
		cout << m - get_min(u, v) + 1 << '\n';
	}
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> nQuery;
	sieve();
	build_MST();
	l[1] = 1;
	fix_root(1);
	init_lca();
	solve_query();
}

Compilation message

pictionary.cpp: In function 'void build_MST()':
pictionary.cpp:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<e.size(); ++i)
                ~^~~~~~~~~
pictionary.cpp: In function 'void fix_root(int)':
pictionary.cpp:84:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
pictionary.cpp: In member function 'bool disjoint_set::uni(int, int)':
pictionary.cpp:41:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 3448 KB Output isn't correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 3688 KB Output isn't correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 3888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 4156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 9532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 73 ms 12128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 112 ms 17100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 193 ms 25200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 192 ms 31564 KB Output isn't correct
2 Halted 0 ms 0 KB -