oj.uz

Submission #935970

# Submission time Handle Problem Language Result Execution time Memory
935970 2024-02-29T20:13:28 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
5 / 100
 581 ms 72796 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];
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) {
			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);
    	if (value) {
    		exit(1);
    	}
    	int tmp1 = get(i, st1, lz1), tmp2 = get(i, st2, lz2), cnt = 0;
    	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);
    		// }
    		twin[i] = fre++;
    		g[tmp2].push_back(twin[i]);
    		used2[tmp2] = 1;
    	}
        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;
    		vector<int> z;
    		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;
    		}
    		for (int j : z) {
    			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);
				}
    		}
    		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);
    		// cout << get_min(2, 2).x << '\n';
    		int left = 0;
    		vector<int> z;
    		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;
    		}
    		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;
    		}
    		for (int j : z) {
    			// cout << 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);
				}
    		}
    		// 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 11 ms 49496 KB Output is correct
2 Correct 11 ms 47452 KB Output is correct
3 Correct 10 ms 47452 KB Output is correct
4 Correct 10 ms 47452 KB Output is correct
5 Correct 11 ms 47452 KB Output is correct
6 Correct 60 ms 50264 KB Output is correct
7 Correct 110 ms 51096 KB Output is correct
8 Correct 581 ms 59728 KB Output is correct
9 Correct 535 ms 59824 KB Output is correct
10 Correct 535 ms 59968 KB Output is correct
11 Correct 527 ms 60920 KB Output is correct
12 Correct 530 ms 64056 KB Output is correct
13 Correct 530 ms 71504 KB Output is correct
14 Correct 556 ms 72796 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 49384 KB Output is correct
2 Correct 10 ms 47452 KB Output is correct
3 Correct 11 ms 49500 KB Output is correct
4 Runtime error 8 ms 43356 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 49384 KB Output is correct
2 Correct 10 ms 47452 KB Output is correct
3 Correct 11 ms 49500 KB Output is correct
4 Runtime error 8 ms 43356 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47300 KB Output is correct
2 Runtime error 8 ms 43376 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 49500 KB Output is correct
2 Correct 10 ms 47416 KB Output is correct
3 Correct 10 ms 47452 KB Output is correct
4 Correct 10 ms 47452 KB Output is correct
5 Runtime error 8 ms 43356 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 12 ms 49500 KB Output is correct
2 Correct 10 ms 47452 KB Output is correct
3 Correct 10 ms 47452 KB Output is correct
4 Correct 10 ms 47452 KB Output is correct
5 Runtime error 8 ms 43356 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 11 ms 49496 KB Output is correct
2 Correct 11 ms 47452 KB Output is correct
3 Correct 10 ms 47452 KB Output is correct
4 Correct 10 ms 47452 KB Output is correct
5 Correct 11 ms 47452 KB Output is correct
6 Correct 60 ms 50264 KB Output is correct
7 Correct 110 ms 51096 KB Output is correct
8 Correct 581 ms 59728 KB Output is correct
9 Correct 535 ms 59824 KB Output is correct
10 Correct 535 ms 59968 KB Output is correct
11 Correct 527 ms 60920 KB Output is correct
12 Correct 530 ms 64056 KB Output is correct
13 Correct 530 ms 71504 KB Output is correct
14 Correct 556 ms 72796 KB Output is correct
15 Correct 10 ms 49384 KB Output is correct
16 Correct 10 ms 47452 KB Output is correct
17 Correct 11 ms 49500 KB Output is correct
18 Runtime error 8 ms 43356 KB Execution failed because the return code was nonzero
19 Halted 0 ms 0 KB -