oj.uz

Submission #435417

# Submission time Handle Problem Language Result Execution time Memory
435417 2021-06-23T10:05:38 Z Muhammetali Keys (IOI21_keys) C++17
9 / 100
 2500 ms 31748 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) x.begin(),x.end()
#define all_r(x) x.rbegin(),x.rend()
#define clr(a) memset((a),0,sizeof(a))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef pair<ll,ll> pl;
typedef vector<ll> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef priority_queue<ll,vl,greater<ll>> pqg;
int R[300000];
vpi adj[300000];
set<int>st,key;
void find(int k){
	st.ins(k);
	key.ins(R[k]);
	for(int i:st){
		for(auto it:adj[i]){
			if(st.count(it.ff)==1 || key.count(it.ss)==0)continue;
			find(it.ff);
			return;
		}
	}
}
vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
	int n=sz(r);
	int m=sz(u);
	vector<int> ans(n,1);
	for(int i=0;i<n;i++)R[i]=r[i];
	for(int i=0;i<m;i++){
		adj[u[i]].pb({v[i],c[i]});
		adj[v[i]].pb({u[i],c[i]});
	}
	int res=INT_MAX;
	for(int i=0;i<n;i++){
		st.clear();
		key.clear();
		bool vis=0;
		for(auto it:adj[i]){
			if(r[i]==it.ss && ans[it.ff]!=1){
				vis=1;
				ans[i]=ans[it.ff];
				break;
			}
		}
		if(!vis){
			find(i);
			ans[i]=sz(st);
		}
		if(res>ans[i])res=ans[i];
	}
	for(int i=0;i<n;i++){
		if(ans[i]==res)ans[i]=1;
		else ans[i]=0;
	}
	return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7344 KB Output is correct
4 Correct 27 ms 7244 KB Output is correct
5 Correct 5 ms 7244 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 12 ms 7364 KB Output is correct
9 Correct 27 ms 7364 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7344 KB Output is correct
4 Correct 27 ms 7244 KB Output is correct
5 Correct 5 ms 7244 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 12 ms 7364 KB Output is correct
9 Correct 27 ms 7364 KB Output is correct
10 Correct 34 ms 7344 KB Output is correct
11 Correct 36 ms 7296 KB Output is correct
12 Correct 39 ms 7372 KB Output is correct
13 Correct 5 ms 7244 KB Output is correct
14 Correct 7 ms 7224 KB Output is correct
15 Incorrect 27 ms 7244 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7344 KB Output is correct
4 Correct 27 ms 7244 KB Output is correct
5 Correct 5 ms 7244 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 12 ms 7364 KB Output is correct
9 Correct 27 ms 7364 KB Output is correct
10 Correct 34 ms 7344 KB Output is correct
11 Correct 36 ms 7296 KB Output is correct
12 Correct 39 ms 7372 KB Output is correct
13 Correct 5 ms 7244 KB Output is correct
14 Correct 7 ms 7224 KB Output is correct
15 Incorrect 27 ms 7244 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7344 KB Output is correct
4 Correct 27 ms 7244 KB Output is correct
5 Correct 5 ms 7244 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 12 ms 7364 KB Output is correct
9 Correct 27 ms 7364 KB Output is correct
10 Execution timed out 2558 ms 31748 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7344 KB Output is correct
4 Correct 27 ms 7244 KB Output is correct
5 Correct 5 ms 7244 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 12 ms 7364 KB Output is correct
9 Correct 27 ms 7364 KB Output is correct
10 Correct 34 ms 7344 KB Output is correct
11 Correct 36 ms 7296 KB Output is correct
12 Correct 39 ms 7372 KB Output is correct
13 Correct 5 ms 7244 KB Output is correct
14 Correct 7 ms 7224 KB Output is correct
15 Incorrect 27 ms 7244 KB Output isn't correct
16 Halted 0 ms 0 KB -