oj.uz

Submission #939923

# Submission time Handle Problem Language Result Execution time Memory
939923 2024-03-07T01:00:55 Z beaboss Keys (IOI21_keys) C++17
39 / 100
 223 ms 48828 KB 
// Source: https://oj.uz/problem/view/IOI21_candies
// 
#include "keys.h"
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = 3e5 + 10;
vpii adj[N];
bool fin[N], vis[N], have[N];
vi vislist, block[N];
vi e;
int here[N], res[N];

int mn = N;

void reset(){
	for (auto val: vislist) {
		have[here[val]]=false;
		vis[val]=false;
	}
	for (auto val: e) block[val].clear();
	vislist.clear();
	e.clear();
}

int bfs(int _) {
	queue<int> q;
	q.push(_);
	vis[_]=true;
	vislist.pb(_);
	int sz = 0;
	while (!q.empty() && sz <= mn) {
		sz++;
		int cur = q.front();
		q.pop();
		// cout << cur << ' ' << here[cur] << endl;
		int key = here[cur];
		for (auto val: block[key]) {
			if (!vis[val]) {
				if (fin[val]) return N; // 
				vislist.pb(val);
				vis[val]=true;
				q.push(val);
				// sz++;
			}
		}

		block[key].clear();

		have[key]=true;
		// cout << ' ' << key << endl;
		for (auto val: adj[cur]) {
			// cout << ' ' << cur << val.f << val.s << key << endl;
			if (vis[val.f]) continue;
			if (have[val.s]) {
				if (fin[val.f]) return N; // 
				vislist.pb(val.f);
				vis[val.f]=true;
				q.push(val.f);
				// sz++;
			} else {
				block[val.s].pb(val.f);
				e.pb(val.s);
			}

		}

	}

	if (sz > mn) return N;

	for (auto val: vislist) res[val] = min(res[val], sz);
		// cout << sz << endl;
	return sz;
}

vi find_reachable(vi c, vi l, vi r, vi v) {


	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	int n = c.size();
	FOR(i, 0, n) {
		here[i] = c[i];
		
		res[i] = N;
	}
	int m = l.size();

	FOR(i, 0, m) {
		adj[l[i]].pb({r[i], v[i]});
		adj[r[i]].pb({l[i], v[i]});
	}

	vi p(2*m);
	FOR(i, 0, n) {
		p[2*i]=l[i];
		p[2*i+1]=r[i];
	}
	// vi p(n);
	// FOR(i, 0, n) p[i]=i;
	shuffle(p.begin(), p.end(), rng);

	for (auto i: p) {
		
		if (!fin[i]) {
			int h = bfs(i);
			res[i] = min(res[i], h);
			// cout << i << h << endl;
			fin[i]=true;
			// cout << i << h << endl;
			mn = min(mn, res[i]);
			reset();
		}
	}

	FOR(i, 0, n) {
		
		if (!fin[i]) {
			int h = bfs(i);
			res[i] = min(res[i], h);
			// cout << i << h << endl;
			fin[i]=true;
			// cout << i << h << endl;
			mn = min(mn, res[i]);
			reset();
		}
	}

	vi ans(n, 0);
	FOR(i, 0, n) {
		if (res[i] == mn) {
			ans[i]=1;
		}
	}

	return ans;

}

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

// 	vi h = find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
// 	for (auto val: h) cout << val << endl;




// }

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17496 KB Output is correct
8 Correct 5 ms 17500 KB Output is correct
9 Correct 4 ms 17500 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17496 KB Output is correct
8 Correct 5 ms 17500 KB Output is correct
9 Correct 4 ms 17500 KB Output is correct
10 Correct 5 ms 17616 KB Output is correct
11 Runtime error 16 ms 35164 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17496 KB Output is correct
8 Correct 5 ms 17500 KB Output is correct
9 Correct 4 ms 17500 KB Output is correct
10 Correct 5 ms 17616 KB Output is correct
11 Runtime error 16 ms 35164 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17496 KB Output is correct
8 Correct 5 ms 17500 KB Output is correct
9 Correct 4 ms 17500 KB Output is correct
10 Correct 186 ms 38772 KB Output is correct
11 Correct 218 ms 48828 KB Output is correct
12 Correct 34 ms 22364 KB Output is correct
13 Correct 187 ms 39008 KB Output is correct
14 Correct 223 ms 41156 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17496 KB Output is correct
8 Correct 5 ms 17500 KB Output is correct
9 Correct 4 ms 17500 KB Output is correct
10 Correct 5 ms 17616 KB Output is correct
11 Runtime error 16 ms 35164 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -