oj.uz

Submission #435427

# Submission time Handle Problem Language Result Execution time Memory
435427 2021-06-23T10:12:34 Z Muhammetali Keys (IOI21_keys) C++17
9 / 100
 2500 ms 31636 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]=max(ans[i],ans[it.ff]);
			}
		}
		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 7428 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 6 ms 7244 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 5 ms 7244 KB Output is correct
8 Correct 23 ms 7364 KB Output is correct
9 Correct 33 ms 7352 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7428 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 6 ms 7244 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 5 ms 7244 KB Output is correct
8 Correct 23 ms 7364 KB Output is correct
9 Correct 33 ms 7352 KB Output is correct
10 Correct 37 ms 7372 KB Output is correct
11 Correct 33 ms 7372 KB Output is correct
12 Correct 38 ms 7372 KB Output is correct
13 Correct 5 ms 7244 KB Output is correct
14 Correct 5 ms 7228 KB Output is correct
15 Incorrect 29 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 7428 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 6 ms 7244 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 5 ms 7244 KB Output is correct
8 Correct 23 ms 7364 KB Output is correct
9 Correct 33 ms 7352 KB Output is correct
10 Correct 37 ms 7372 KB Output is correct
11 Correct 33 ms 7372 KB Output is correct
12 Correct 38 ms 7372 KB Output is correct
13 Correct 5 ms 7244 KB Output is correct
14 Correct 5 ms 7228 KB Output is correct
15 Incorrect 29 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 7428 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 6 ms 7244 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 5 ms 7244 KB Output is correct
8 Correct 23 ms 7364 KB Output is correct
9 Correct 33 ms 7352 KB Output is correct
10 Execution timed out 2564 ms 31636 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 7428 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 6 ms 7244 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 5 ms 7244 KB Output is correct
8 Correct 23 ms 7364 KB Output is correct
9 Correct 33 ms 7352 KB Output is correct
10 Correct 37 ms 7372 KB Output is correct
11 Correct 33 ms 7372 KB Output is correct
12 Correct 38 ms 7372 KB Output is correct
13 Correct 5 ms 7244 KB Output is correct
14 Correct 5 ms 7228 KB Output is correct
15 Incorrect 29 ms 7244 KB Output isn't correct
16 Halted 0 ms 0 KB -