oj.uz

Submission #935989

# Submission time Handle Problem Language Result Execution time Memory
935989 2024-02-29T21:04:15 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
5 / 100
 638 ms 74096 KB 
#include <bits/stdc++.h>
#include "plants.h"

#define x first
#define y second

using ll = long long;
 
using namespace std;
 
const int N = 1 << 19;
vector<int> g[N];
int st1[2 * N], st2[2 * N], lz1[2 * N], lz2[2 * N], twin[N], tin[N], tout[N], timer = 1, fndl[2 * N], used1[N], used2[N], fre = N / 2, deg[N], used3[N], used4[N];
pair<int, int> fnd[2 * N];

void push(int i, int st[], int lz[]) {
	if (lz[i] != -1) {
		st[2 * i + 1] = lz[i];
		st[2 * i + 2] = lz[i];
		lz[2 * i + 1] = lz[i];
		lz[2 * i + 2] = lz[i];
		lz[i] = -1;
	}
}

void set_seg(int l, int r, int x, int st[], int lz[], int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		st[i] = x;
		lz[i] = x;
		return;
	}
	if (l1 > r || r1 < l) {
		return;
	}
	push(i, st, lz);
	set_seg(l, r, x, st, lz, l1, (l1 + r1) / 2, 2 * i + 1);
	set_seg(l, r, x, st, lz, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
	st[i] = min(st[2 * i + 1], st[2 * i + 2]);
}

int get(int ind, int st[], int lz[], int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 == ind && r1 == ind) {
		return st[i];
	}
	if (l1 > ind || r1 < ind) {
		return INT32_MAX;
	}
	push(i, st, lz);
	return min(get(ind, st, lz, l1, (l1 + r1) / 2, 2 * i + 1), get(ind, st, lz, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}

void push(int i) {
	fnd[2 * i + 1].x += fndl[i];
	fnd[2 * i + 2].x += fndl[i];
	fndl[2 * i + 1] += fndl[i];
	fndl[2 * i + 2] += fndl[i];
	fndl[i] = 0;
}

void add_seg(int l, int r, int x, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		// cout << fnd[i].x << ' ';
		fnd[i].x += x;
		fndl[i] += x;
		// cout << fnd[i].x << ' ' << i << '\n';
		return;
	}
	if (l1 > r || r1 < l) {
		return;
	}
	push(i);
	add_seg(l, r, x, l1, (l1 + r1) / 2, 2 * i + 1);
	add_seg(l, r, x, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
	fnd[i] = min(fnd[2 * i + 1], fnd[2 * i + 2]);
}

pair<int, int> get_min(int l, int r, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		// cout << fnd[i].x << ' ' << fnd[i].y << ' ' << i << '\n';
		return fnd[i];
	}
	if (l1 > r || r1 < l) {
		return {INT32_MAX, -1};
	}
	push(i);
	return min(get_min(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get_min(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}

void dfs(int s, int p) {
	tin[s] = timer++;
	for (int i : g[s]) {
		if (i != p) {
			dfs(i, s);
		}
	}
	tout[s] = timer++;
}
 
void init(int k, vector<int> r) {
    int n = r.size();
    int ok = 0;
    for (int i = 0; i < 2 * N; i++) {
    	st1[i] = -1;
    	st2[i] = -1;
    	lz1[i] = -1;
    	lz2[i] = -1;
    }
    for (int i = 0; i < N; i++) {
    	twin[i] = -1;
    }
    for (int i = 0; i < N; i++) {
    	fnd[i + N - 1].y = i;
    }
    for (int i = 0; i < n; i++) {
    	add_seg(i, i, r[i]);
		if (r[i] == 0) {
			used3[i] = 1;
			if (i + k > n) {
				add_seg(i + 1, n - 1, 1);
				add_seg(0, i + k - n - 1, 1);
			} else {
				add_seg(i + 1, i + k - 1, 1);
			}
		}
    }
    while (ok < n) {
    	auto [value, i] = get_min(0, n - 1);
    	// cout << value << ' ' << i << '\n';
    	// assert(value == 0);
    	// cout << i << '\n';
    	// if (!used3[i]) {
    	// 	cout << "! " << ok << ' ' << i << '\n';
    	// }
    	// if (used4[i]) {
    	// 	cout << "!! " << i << '\n';
    	// }
    	used4[i] = 1;
    	if (value) {
    		// cout << value << ' ' << i << '\n';
    		exit(1);
    	}
    	int tmp1 = get(i, st1, lz1), tmp2 = get(i, st2, lz2), cnt = 0;
    	if (tmp1 != -1) {
    		for (int j : g[tmp1]) {
    			if (j == tmp2) {
    				tmp1 = -1;
    				break;
    			}
    		}
    	}
    	if (tmp2 != -1) {
    		for (int j : g[tmp2]) {
    			if (j == tmp1) {
    				tmp2 = -1;
    				break;
    			}
    		}
    	}
    	if (tmp1 != -1 && !used1[tmp1]) {
    		g[tmp1].push_back(i);
    		deg[i]++;
    		used1[tmp1] = 1;
    		if (tmp1 == tmp2) {
    			used2[tmp2] = 1;
    		}
    		cnt++;
    		if (twin[tmp1] != -1) {
    			twin[i] = fre++;
    			g[twin[tmp1]].push_back(twin[i]);
    			cnt++;
    		}
    	}
    	if (tmp2 != -1 && !used2[tmp2] && !cnt) {
    		g[tmp2].push_back(i);
    		deg[i]++;
    		used2[tmp2] = 1;
    		if (twin[tmp2] != -1) {
    			twin[i] = fre++;
    			g[twin[tmp2]].push_back(twin[i]);
    		}
    	} else if (tmp2 != -1 && !used2[tmp2]) {
    		// assert(cnt == 1);
    		if (cnt != 1) {
    			// exit(1);
    			// cout << i << ' ' << tmp1 << ' ' << tmp2 << '\n';
    		}
    		twin[i] = fre++;
    		g[tmp2].push_back(twin[i]);
    		used2[tmp2] = 1;
    	}
    	vector<int> z;
        if (i + k - 1 < n) {
    		set_seg(i + 1, i + k - 1, i, st2, lz2);
    		add_seg(i + 1, i + k - 1, -1);
    	} else {
    		set_seg(i + 1, n - 1, i, st2, lz2);
    		set_seg(0, i + k - 1 - n, i, st2, lz2);
    		add_seg(i + 1, n - 1, -1);
    		add_seg(0, i + k - 1 - n, -1);
    	}
    	if (i >= k - 1) {
    		add_seg(i - k + 1, i - 1, -1);
    		int left = i - k + 1;
    		while (left <= i - 1 && !get_min(left, i - 1).x) {
    			z.push_back(get_min(left, i - 1).y);
    			assert(left <= z.back());
    			left = z.back() + 1;
    		}
    		set_seg(i - k + 1, i - 1, i, st1, lz1);
    	} else {
    		add_seg(0, i - 1, -1);
    		set_seg(0, i - 1, i, st1, lz1);
    		add_seg(n + 1 - k + i, n - 1, -1);
    		set_seg(n + 1 - k + i, n - 1, i, st1, lz1);
    		int left = 0;
    		while (left <= i - 1 && !get_min(left, i - 1).x) {
    			// cout << "!\n";
    			z.push_back(get_min(left, i - 1).y);
    			assert(left <= z.back());
    			left = z.back() + 1;
    		}
    		// cout << left << ' ' << get_min(left, i - 1).x << '\n';
    		left = n + 1 - k + i;
    		while (left <= n - 1 && !get_min(left, n - 1).x) {
    			z.push_back(get_min(left, n - 1).y);
    			assert(left <= z.back());
    			left = z.back() + 1;
    		}
    	}
    	if (i + k - 1 < n) {
    		int left = i + 1;
    		while (left <= i + k - 1 && !get_min(left, i + k - 1).x) {
    			z.push_back(get_min(left, i + k - 1).y);
    			assert(left <= z.back());
    			left = z.back() + 1;
    		}
    	} else {
    		int left = i + 1;
    		while (left <= n - 1 && !get_min(left, n - 1).x) {
    			z.push_back(get_min(left, n - 1).y);
    			assert(left <= z.back());
    			left = z.back() + 1;
    		}
    		left = 0;
    		while (left <= i + k - 1 - n && !get_min(left, i + k - 1 - n).x) {
    			z.push_back(get_min(left, i + k - 1 - n).y);
    			assert(left <= z.back());
    			left = z.back() + 1;
    		}
    	}
    	for (int j : z) {
    		// cout << j << ' ';
    		if (!used3[j]) {
				if (j + k > n) {
					add_seg(j + 1, n - 1, 1);
					add_seg(0, j + k - n - 1, 1);
				} else {
					add_seg(j + 1, j + k - 1, 1);
				}
				used3[j] = 1;
			}
		}
		// cout << '\n';
        // for (int j = i - 1; j > i - k; j--) {
        //     if (j >= 0) {
        //         nw[j]--;
        //         tmp1[j] = i;
        //     } else {
        //         nw[j + n]--;
        //         tmp1[j + n] = i;
        //     }
        // }
        // for (int j = i + 1; j < i + k; j++) {
        //     if (j < n) {
        //         tmp2[j] = i;
        //     } else {
        //         tmp2[j - n] = i;
        //     }
        // }
        add_seg(i, i, INT32_MAX / 2);
        // cout << get_min(i, i).x << '\n';
        // nw[i] = INT32_MAX / 2;
    	ok++;
    }
    for (int i = 0; i < N; i++) {
	    if (!tin[i] && !deg[i]) {
	    	dfs(i, -1);
	    }
    }
}
 
int compare_plants(int x, int y) {
	vector<int> xx(1, x), yy(1, y);
	if (twin[x] != -1) {
		xx.push_back(twin[x]);
	}
	if (twin[y] != -1) {
		yy.push_back(twin[y]);
	}
	for (int y1 : yy) {
		for (int x1 : xx) {
			if (tin[y1] < tin[x1] && tout[y1] > tin[x1]) {
				return -1;
			}
		}
	}
    // if (clc[y][x]) {
    //     return -1;
    // }
    for (int y1 : xx) {
		for (int x1 : yy) {
			if (tin[y1] < tin[x1] && tout[y1] > tin[x1]) {
				return 1;
			}
		}
	}
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 53596 KB Output is correct
2 Correct 11 ms 51548 KB Output is correct
3 Correct 11 ms 51580 KB Output is correct
4 Correct 11 ms 51548 KB Output is correct
5 Correct 11 ms 51548 KB Output is correct
6 Correct 66 ms 54368 KB Output is correct
7 Correct 112 ms 55376 KB Output is correct
8 Correct 618 ms 63620 KB Output is correct
9 Correct 600 ms 64108 KB Output is correct
10 Correct 591 ms 64080 KB Output is correct
11 Correct 633 ms 65276 KB Output is correct
12 Correct 638 ms 68416 KB Output is correct
13 Correct 587 ms 72676 KB Output is correct
14 Correct 599 ms 74096 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 53596 KB Output is correct
2 Correct 11 ms 51548 KB Output is correct
3 Correct 11 ms 53596 KB Output is correct
4 Correct 11 ms 51548 KB Output is correct
5 Correct 14 ms 51548 KB Output is correct
6 Incorrect 18 ms 51748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 53596 KB Output is correct
2 Correct 11 ms 51548 KB Output is correct
3 Correct 11 ms 53596 KB Output is correct
4 Correct 11 ms 51548 KB Output is correct
5 Correct 14 ms 51548 KB Output is correct
6 Incorrect 18 ms 51748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 51548 KB Output is correct
2 Runtime error 8 ms 47416 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 53848 KB Output is correct
2 Correct 12 ms 51548 KB Output is correct
3 Correct 11 ms 51548 KB Output is correct
4 Correct 11 ms 51544 KB Output is correct
5 Runtime error 9 ms 47452 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 53464 KB Output is correct
2 Correct 11 ms 51548 KB Output is correct
3 Correct 11 ms 51504 KB Output is correct
4 Correct 12 ms 51548 KB Output is correct
5 Runtime error 9 ms 47452 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 53596 KB Output is correct
2 Correct 11 ms 51548 KB Output is correct
3 Correct 11 ms 51580 KB Output is correct
4 Correct 11 ms 51548 KB Output is correct
5 Correct 11 ms 51548 KB Output is correct
6 Correct 66 ms 54368 KB Output is correct
7 Correct 112 ms 55376 KB Output is correct
8 Correct 618 ms 63620 KB Output is correct
9 Correct 600 ms 64108 KB Output is correct
10 Correct 591 ms 64080 KB Output is correct
11 Correct 633 ms 65276 KB Output is correct
12 Correct 638 ms 68416 KB Output is correct
13 Correct 587 ms 72676 KB Output is correct
14 Correct 599 ms 74096 KB Output is correct
15 Correct 11 ms 53596 KB Output is correct
16 Correct 11 ms 51548 KB Output is correct
17 Correct 11 ms 53596 KB Output is correct
18 Correct 11 ms 51548 KB Output is correct
19 Correct 14 ms 51548 KB Output is correct
20 Incorrect 18 ms 51748 KB Output isn't correct
21 Halted 0 ms 0 KB -