#include <vector>
#include <queue>
#include <iostream>
using namespace std;
const int N=3000;
vector<pair<int,int>> edge_with_key[N];
bool used_key[N];
bool marked[N];
int par[N];
vector<int> comp[N];
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();
int mi=2*n;
int ed=u.size();
vector<int> ap;
for(int i=0;i<ed;i++)
edge_with_key[c[i]].push_back({u[i],v[i]});
for(int st=0;st<n;st++)
{
for(int ke=0;ke<n;ke++)
{
par[ke]=ke;
comp[ke]={ke};
used_key[ke]=marked[ke]=0;
}
queue<int> keys;
keys.push(r[st]);
used_key[r[st]]=1;
marked[st]=1;
while(keys.size())
{
int f=keys.front();
for(auto [s,e]:edge_with_key[f])
{
int ps=par[s];
int pe=par[e];
if(ps==pe)
continue;
if(pe==(par[st]))
swap(ps,pe);
// cout<<"Hello "<<endl;
// cout<<ps<<' '<<pe<<endl;
// cout<<"Comp ";
for(auto ip:comp[pe])
{
comp[ps].push_back(ip);
par[ip]=ps;
if(ps==par[st] and !used_key[r[ip]])
{
used_key[r[ip]]=1;
keys.push(r[ip]);
}
}
comp[pe].clear();
// for(auto it:comp[ps])
// {
// cout<<it<<' ';
// }
// cout<<endl;
}
keys.pop();
}
int cnt=0;
for(int ke=0;ke<n;ke++)
cnt+=(par[ke]==par[st]);
mi=min(mi,cnt);
ap.push_back(cnt);
}
vector<int> cp;
for(int i=0;i<n;i++)
{
cp.push_back((ap[i]==mi));
}
return cp;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
668 KB |
Output is correct |
5 |
Correct |
0 ms |
580 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
668 KB |
Output is correct |
5 |
Correct |
0 ms |
580 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
696 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
584 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
580 KB |
Output is correct |
22 |
Correct |
1 ms |
600 KB |
Output is correct |
23 |
Correct |
1 ms |
600 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
2 ms |
580 KB |
Output is correct |
26 |
Correct |
2 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
668 KB |
Output is correct |
5 |
Correct |
0 ms |
580 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
696 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
584 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
580 KB |
Output is correct |
22 |
Correct |
1 ms |
600 KB |
Output is correct |
23 |
Correct |
1 ms |
600 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
2 ms |
580 KB |
Output is correct |
26 |
Correct |
2 ms |
604 KB |
Output is correct |
27 |
Correct |
58 ms |
5972 KB |
Output is correct |
28 |
Correct |
56 ms |
5968 KB |
Output is correct |
29 |
Correct |
56 ms |
6048 KB |
Output is correct |
30 |
Correct |
15 ms |
2392 KB |
Output is correct |
31 |
Correct |
3 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
4 ms |
672 KB |
Output is correct |
34 |
Correct |
22 ms |
4444 KB |
Output is correct |
35 |
Correct |
22 ms |
3632 KB |
Output is correct |
36 |
Correct |
98 ms |
12664 KB |
Output is correct |
37 |
Correct |
106 ms |
12624 KB |
Output is correct |
38 |
Correct |
167 ms |
15956 KB |
Output is correct |
39 |
Correct |
180 ms |
15948 KB |
Output is correct |
40 |
Correct |
14 ms |
1624 KB |
Output is correct |
41 |
Correct |
33 ms |
4188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
668 KB |
Output is correct |
5 |
Correct |
0 ms |
580 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
696 KB |
Output is correct |
10 |
Runtime error |
79 ms |
27108 KB |
Execution killed with signal 11 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
668 KB |
Output is correct |
5 |
Correct |
0 ms |
580 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
696 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
584 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
580 KB |
Output is correct |
22 |
Correct |
1 ms |
600 KB |
Output is correct |
23 |
Correct |
1 ms |
600 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
2 ms |
580 KB |
Output is correct |
26 |
Correct |
2 ms |
604 KB |
Output is correct |
27 |
Correct |
58 ms |
5972 KB |
Output is correct |
28 |
Correct |
56 ms |
5968 KB |
Output is correct |
29 |
Correct |
56 ms |
6048 KB |
Output is correct |
30 |
Correct |
15 ms |
2392 KB |
Output is correct |
31 |
Correct |
3 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
4 ms |
672 KB |
Output is correct |
34 |
Correct |
22 ms |
4444 KB |
Output is correct |
35 |
Correct |
22 ms |
3632 KB |
Output is correct |
36 |
Correct |
98 ms |
12664 KB |
Output is correct |
37 |
Correct |
106 ms |
12624 KB |
Output is correct |
38 |
Correct |
167 ms |
15956 KB |
Output is correct |
39 |
Correct |
180 ms |
15948 KB |
Output is correct |
40 |
Correct |
14 ms |
1624 KB |
Output is correct |
41 |
Correct |
33 ms |
4188 KB |
Output is correct |
42 |
Runtime error |
79 ms |
27108 KB |
Execution killed with signal 11 |
43 |
Halted |
0 ms |
0 KB |
- |