oj.uz

Submission #347779

# Submission time Handle Problem Language Result Execution time Memory
347779 2021-01-13T12:10:26 Z jesus_coconut Pictionary (COCI18_pictionary) C++17
140 / 140
 630 ms 31000 KB 
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

struct DSU {
	vector<int> par, rank, setsize;
	int numsets;

	explicit DSU(int n) {
		par.assign(n, 0);
		iota(begin(par), end(par), 0);
		rank.assign(n, 0);
		setsize.assign(n, 1);
		numsets = n;
	}

	void reset() {
        iota(begin(par), end(par), 0);
        fill(begin(rank), end(rank), 0);
        fill(begin(setsize), end(setsize), 0);
	}

	int findSet(int x) { return (par[x] == x) ? x : (par[x] = findSet(par[x])); }

	bool sameSet(int x, int y) { return findSet(x) == findSet(y); }

	bool unite(int x, int y) {
		if (sameSet(x, y)) return false;
		x = findSet(x), y = findSet(y);
		if (rank[x] > rank[y]) swap(x, y);
		par[x] = y;
		if (rank[x] == rank[y]) ++rank[y];
		setsize[y] += setsize[x];
		--numsets;
		return true;
	}
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, Q;
    cin >> n >> m >> Q;
    vector<pair<int, int>> q(Q);
    vector<vector<pair<int, pair<int, int>>>> mids(m + 10);
    for (int i = 0; i < Q; ++i) {
        mids[(1 + m) / 2].emplace_back(i, make_pair(1, m));
    }
    for (auto &[a, b] : q) cin >> a >> b;

    vector<pair<int, int>> bounds(Q, {1, m});
    vector<int> sol(Q, -1);
    int done = 0;
    DSU dsu(n + 10);
    while (done < Q) {
        vector<vector<pair<int, pair<int, int>>>> nxt(m + 10);
        dsu.reset();
        for (int i = 1; i <= m; ++i) {
            for (int j = 2 * (m - i + 1); j <= n; j += m - i + 1) {
                dsu.unite(m - i + 1, j);
            }
            for (auto [a, bd] : mids[i]) {
                int cmid = (bd.F + bd.S) / 2;
                if (dsu.sameSet(q[a].F, q[a].S)) {
                    if (bd.F == bd.S) {
                        sol[a] = i;
                        done++;
                    } else {
                        nxt[cmid].emplace_back(a, make_pair(bd.F, i));
                    }
                } else {
                    nxt[cmid].emplace_back(a, make_pair(i + 1, bd.S));
                }
            }
        }
        mids = nxt;

    }

    for (int i = 0; i < Q; ++i) {
        cout << sol[i] << '\n';
    }

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1040 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2908 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10752 KB Output is correct
2 Correct 48 ms 8224 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 15020 KB Output is correct
2 Correct 75 ms 12084 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 11276 KB Output is correct
2 Correct 125 ms 9944 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 11788 KB Output is correct
2 Correct 117 ms 8980 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 18336 KB Output is correct
2 Correct 241 ms 11800 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 11880 KB Output is correct
2 Correct 383 ms 20780 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 24920 KB Output is correct
2 Correct 450 ms 21700 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 31000 KB Output is correct
2 Correct 530 ms 24784 KB Output is correct