# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
496108 |
2021-12-20T16:56:16 Z |
Half |
Keys (IOI21_keys) |
C++17 |
|
3000 ms |
24812 KB |
#include <vector>
#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"DEBUG "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size(), m = u.size();
vector<pair<int, int>> adj[n];
for(int i = 0; i < m; i++){
adj[u[i]].pb(mp(v[i], c[i]));
adj[v[i]].pb(mp(u[i], c[i]));
}
int mn = n+1;
vector<int> mnr;
for(int i = 0; i < n; i++){
queue<pair<pair<int, int>, int> > q;
q.push(mp(mp(i, n), -1));
bool visited[n];
memset(visited, false, sizeof visited);
bool keys[n+1];
memset(keys, false, sizeof keys);
keys[n] = true;
int cnt = 0;
while(!q.empty()){
pair<pair<int, int>, int> nxt = q.front();
q.pop();
int j = nxt.ff.ff, ky = nxt.ff.ss, rnd = nxt.ss;
if(visited[j])
continue;
if(rnd == cnt)
break;
if(!keys[ky]){
q.push(mp(mp(j, ky), cnt));
continue;
}
keys[r[j]] = true;
visited[j] = true;
for(auto adpr : adj[j])
q.push(mp(adpr, cnt));
cnt++;
}
if(cnt < mn){
mn = cnt;
mnr.clear();
mnr.pb(i);
}else if (cnt == mn){
mnr.pb(i);
}
}
std::vector<int> ans(r.size(), 0);
for(auto i : mnr)
ans[i] = 1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
288 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
288 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
292 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
3 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
288 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
2 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
6 ms |
308 KB |
Output is correct |
24 |
Correct |
6 ms |
288 KB |
Output is correct |
25 |
Correct |
3 ms |
332 KB |
Output is correct |
26 |
Correct |
4 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
288 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
292 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
3 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
288 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
2 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
6 ms |
308 KB |
Output is correct |
24 |
Correct |
6 ms |
288 KB |
Output is correct |
25 |
Correct |
3 ms |
332 KB |
Output is correct |
26 |
Correct |
4 ms |
204 KB |
Output is correct |
27 |
Correct |
49 ms |
520 KB |
Output is correct |
28 |
Correct |
51 ms |
516 KB |
Output is correct |
29 |
Correct |
46 ms |
580 KB |
Output is correct |
30 |
Correct |
173 ms |
380 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
296 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
40 ms |
376 KB |
Output is correct |
35 |
Correct |
295 ms |
388 KB |
Output is correct |
36 |
Correct |
2163 ms |
608 KB |
Output is correct |
37 |
Execution timed out |
3070 ms |
468 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
288 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Execution timed out |
3094 ms |
24812 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
288 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
292 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
3 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
288 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
2 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
6 ms |
308 KB |
Output is correct |
24 |
Correct |
6 ms |
288 KB |
Output is correct |
25 |
Correct |
3 ms |
332 KB |
Output is correct |
26 |
Correct |
4 ms |
204 KB |
Output is correct |
27 |
Correct |
49 ms |
520 KB |
Output is correct |
28 |
Correct |
51 ms |
516 KB |
Output is correct |
29 |
Correct |
46 ms |
580 KB |
Output is correct |
30 |
Correct |
173 ms |
380 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
296 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
40 ms |
376 KB |
Output is correct |
35 |
Correct |
295 ms |
388 KB |
Output is correct |
36 |
Correct |
2163 ms |
608 KB |
Output is correct |
37 |
Execution timed out |
3070 ms |
468 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |