oj.uz

답안 #435455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435455 2021-06-23T10:42:30 Z Muhammetali 열쇠 (IOI21_keys) C++17
20 / 100
 2500 ms 59504 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[300000],key[300000];
void find(int k,int ind){
	st[ind].ins(k);
	key[ind].ins(R[k]);
	for(int i:st[ind]){
		for(auto it:adj[i]){
			if(st[ind].count(it.ff)==1 || key[ind].count(it.ss)==0)continue;
			find(it.ff,ind);
			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++){
		vi f;
		st[i].ins(i);
		key[i].ins(r[i]);
		for(auto it:adj[i]){
			if(r[i]==it.ss){
				if(ans[it.ff]!=1){
					for(int j:st[it.ff]){
						st[i].ins(j);
						key[i].ins(R[j]);
					}
				}
				else find(it.ff,i);
			}
		}
		ans[i]=sz(st[i]);
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35532 KB Output is correct
2 Correct 24 ms 35472 KB Output is correct
3 Correct 22 ms 35456 KB Output is correct
4 Correct 66 ms 36176 KB Output is correct
5 Correct 25 ms 35408 KB Output is correct
6 Correct 22 ms 35404 KB Output is correct
7 Correct 22 ms 35504 KB Output is correct
8 Correct 35 ms 36036 KB Output is correct
9 Correct 69 ms 36448 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35532 KB Output is correct
2 Correct 24 ms 35472 KB Output is correct
3 Correct 22 ms 35456 KB Output is correct
4 Correct 66 ms 36176 KB Output is correct
5 Correct 25 ms 35408 KB Output is correct
6 Correct 22 ms 35404 KB Output is correct
7 Correct 22 ms 35504 KB Output is correct
8 Correct 35 ms 36036 KB Output is correct
9 Correct 69 ms 36448 KB Output is correct
10 Correct 52 ms 36424 KB Output is correct
11 Correct 57 ms 36460 KB Output is correct
12 Correct 57 ms 36432 KB Output is correct
13 Correct 23 ms 35496 KB Output is correct
14 Correct 23 ms 35404 KB Output is correct
15 Correct 59 ms 36328 KB Output is correct
16 Correct 21 ms 35404 KB Output is correct
17 Correct 23 ms 35532 KB Output is correct
18 Correct 23 ms 35668 KB Output is correct
19 Correct 23 ms 35464 KB Output is correct
20 Correct 25 ms 35664 KB Output is correct
21 Correct 93 ms 38296 KB Output is correct
22 Correct 29 ms 36028 KB Output is correct
23 Correct 79 ms 37580 KB Output is correct
24 Correct 84 ms 37608 KB Output is correct
25 Correct 117 ms 38788 KB Output is correct
26 Correct 109 ms 38816 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35532 KB Output is correct
2 Correct 24 ms 35472 KB Output is correct
3 Correct 22 ms 35456 KB Output is correct
4 Correct 66 ms 36176 KB Output is correct
5 Correct 25 ms 35408 KB Output is correct
6 Correct 22 ms 35404 KB Output is correct
7 Correct 22 ms 35504 KB Output is correct
8 Correct 35 ms 36036 KB Output is correct
9 Correct 69 ms 36448 KB Output is correct
10 Correct 52 ms 36424 KB Output is correct
11 Correct 57 ms 36460 KB Output is correct
12 Correct 57 ms 36432 KB Output is correct
13 Correct 23 ms 35496 KB Output is correct
14 Correct 23 ms 35404 KB Output is correct
15 Correct 59 ms 36328 KB Output is correct
16 Correct 21 ms 35404 KB Output is correct
17 Correct 23 ms 35532 KB Output is correct
18 Correct 23 ms 35668 KB Output is correct
19 Correct 23 ms 35464 KB Output is correct
20 Correct 25 ms 35664 KB Output is correct
21 Correct 93 ms 38296 KB Output is correct
22 Correct 29 ms 36028 KB Output is correct
23 Correct 79 ms 37580 KB Output is correct
24 Correct 84 ms 37608 KB Output is correct
25 Correct 117 ms 38788 KB Output is correct
26 Correct 109 ms 38816 KB Output is correct
27 Execution timed out 2576 ms 40024 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35532 KB Output is correct
2 Correct 24 ms 35472 KB Output is correct
3 Correct 22 ms 35456 KB Output is correct
4 Correct 66 ms 36176 KB Output is correct
5 Correct 25 ms 35408 KB Output is correct
6 Correct 22 ms 35404 KB Output is correct
7 Correct 22 ms 35504 KB Output is correct
8 Correct 35 ms 36036 KB Output is correct
9 Correct 69 ms 36448 KB Output is correct
10 Execution timed out 2575 ms 59504 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35532 KB Output is correct
2 Correct 24 ms 35472 KB Output is correct
3 Correct 22 ms 35456 KB Output is correct
4 Correct 66 ms 36176 KB Output is correct
5 Correct 25 ms 35408 KB Output is correct
6 Correct 22 ms 35404 KB Output is correct
7 Correct 22 ms 35504 KB Output is correct
8 Correct 35 ms 36036 KB Output is correct
9 Correct 69 ms 36448 KB Output is correct
10 Correct 52 ms 36424 KB Output is correct
11 Correct 57 ms 36460 KB Output is correct
12 Correct 57 ms 36432 KB Output is correct
13 Correct 23 ms 35496 KB Output is correct
14 Correct 23 ms 35404 KB Output is correct
15 Correct 59 ms 36328 KB Output is correct
16 Correct 21 ms 35404 KB Output is correct
17 Correct 23 ms 35532 KB Output is correct
18 Correct 23 ms 35668 KB Output is correct
19 Correct 23 ms 35464 KB Output is correct
20 Correct 25 ms 35664 KB Output is correct
21 Correct 93 ms 38296 KB Output is correct
22 Correct 29 ms 36028 KB Output is correct
23 Correct 79 ms 37580 KB Output is correct
24 Correct 84 ms 37608 KB Output is correct
25 Correct 117 ms 38788 KB Output is correct
26 Correct 109 ms 38816 KB Output is correct
27 Execution timed out 2576 ms 40024 KB Time limit exceeded
28 Halted 0 ms 0 KB -