oj.uz

답안 #811245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
811245 2023-08-07T03:05:19 Z penguinman 열쇠 (IOI21_keys) C++17
37 / 100
 3000 ms 124336 KB 
#include <vector>

#include <bits/stdc++.h>
 
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;
 
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

constexpr ll inf = (1ll<<60);

struct directed_graph{
	ll N;
	vii edge;
	vii revedge;
	vi par;
	vii member;
	directed_graph(ll n): N(n){
		edge.resize(N);
		revedge.resize(N);
	}
	void add_edge(ll u, ll v){
		edge[u].pb(v);
		revedge[v].pb(u);
	}
	vi ord, rev;
	vector<bool> flag;
	void dfs1(ll now){
		flag[now] = true;
		for(auto next: edge[now]){
			if(!flag[next]) dfs1(next);
		}
		ord.pb(now);
	}
	void dfs2(ll now, ll root){
		rev[now] = root;
		for(auto next: revedge[now]){
			if(rev[next] == -1) dfs2(next, root);
		}
	}
	vi SCC(){
		flag.resize(N);
		rev.resize(N,-1);
		ll cnt = 0;
		rep(i,0,N){
			if(!flag[i]) dfs1(i);
		}
		reverse(all(ord));
		for(auto i: ord){
			if(rev[i] == -1) dfs2(i, i);
		}
		return rev;
	}
};

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	ll N = r.size();
	vii edge(N), key(N);
	rep(i,0,u.size()){
		edge[u[i]].pb(v[i]);
		edge[v[i]].pb(u[i]);
		key[u[i]].pb(c[i]);
		key[v[i]].pb(c[i]);
	}
	vi par(N);
	ll Rmax = *max_element(all(r))+1;
	vector<vector<bool>> obtained(N,vector<bool>(Rmax));
	rep(i,0,N){
		par[i] = i;
		obtained[i][r[i]] = true;
	}
	while(true){
		directed_graph G(N);
		rep(i,0,N){
			rep(j,0,edge[i].size()){
				ll next = edge[i][j];
				if(par[next] == par[i]) continue;
				if(!obtained[par[i]][key[i][j]]) continue;
				G.add_edge(par[i],par[next]);
			}
		}
		{
			vi v;
			vector<bool> flag(N);
			rep(i,0,N){
				if(par[i] == i){
					if(G.edge[i].empty()){
						v.pb(i);
						flag[i] = true;
					}
				}
			}
			if(!v.empty()){
				vi member(N);
				rep(i,0,N){
					if(flag[par[i]]) member[par[i]]++;
				}
				ll min = inf;
				rep(i,0,N){
					if(member[i]) min = std::min(min, member[i]);
				}
				vector<int> ans(N);
				rep(i,0,N){
					if(member[par[i]] == min) ans[i] = 1;
				}
				return ans;
			}
		}
		par = G.SCC();
		rep(i,0,N) obtained[par[i]][r[i]] = true;
	}
}

Compilation message

keys.cpp: In member function 'vi directed_graph::SCC()':
keys.cpp:58:6: warning: unused variable 'cnt' [-Wunused-variable]
   58 |   ll cnt = 0;
      |      ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 264 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 300 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 1 ms 300 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 264 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 300 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 1 ms 300 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 3 ms 1464 KB Output is correct
28 Correct 2 ms 1364 KB Output is correct
29 Correct 2 ms 1364 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 764 KB Output is correct
32 Correct 1 ms 300 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 1 ms 724 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 2 ms 1108 KB Output is correct
37 Correct 2 ms 1108 KB Output is correct
38 Correct 2 ms 1340 KB Output is correct
39 Correct 2 ms 1364 KB Output is correct
40 Correct 1 ms 596 KB Output is correct
41 Correct 2 ms 724 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 220 ms 52320 KB Output is correct
11 Execution timed out 3077 ms 124336 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 264 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 300 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 1 ms 300 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 3 ms 1464 KB Output is correct
28 Correct 2 ms 1364 KB Output is correct
29 Correct 2 ms 1364 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 764 KB Output is correct
32 Correct 1 ms 300 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 1 ms 724 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 2 ms 1108 KB Output is correct
37 Correct 2 ms 1108 KB Output is correct
38 Correct 2 ms 1340 KB Output is correct
39 Correct 2 ms 1364 KB Output is correct
40 Correct 1 ms 596 KB Output is correct
41 Correct 2 ms 724 KB Output is correct
42 Correct 220 ms 52320 KB Output is correct
43 Execution timed out 3077 ms 124336 KB Time limit exceeded
44 Halted 0 ms 0 KB -