#include <vector>
#include <queue>
#include <iostream>
using namespace std;
const int N=300000+2;
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(comp[ps].size()<comp[pe].size())
swap(ps,pe);
for(auto ip:comp[pe])
{
comp[ps].push_back(ip);
par[ip]=ps;
}
for(auto ip:comp[pe])
{
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 |
6 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 4 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 5 |
Correct |
4 ms |
16228 KB |
Output is correct |
| 6 |
Correct |
4 ms |
16228 KB |
Output is correct |
| 7 |
Correct |
4 ms |
16480 KB |
Output is correct |
| 8 |
Correct |
5 ms |
16232 KB |
Output is correct |
| 9 |
Correct |
5 ms |
16228 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 4 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 5 |
Correct |
4 ms |
16228 KB |
Output is correct |
| 6 |
Correct |
4 ms |
16228 KB |
Output is correct |
| 7 |
Correct |
4 ms |
16480 KB |
Output is correct |
| 8 |
Correct |
5 ms |
16232 KB |
Output is correct |
| 9 |
Correct |
5 ms |
16228 KB |
Output is correct |
| 10 |
Correct |
4 ms |
16232 KB |
Output is correct |
| 11 |
Correct |
4 ms |
16352 KB |
Output is correct |
| 12 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 13 |
Correct |
4 ms |
16052 KB |
Output is correct |
| 14 |
Correct |
4 ms |
16224 KB |
Output is correct |
| 15 |
Incorrect |
4 ms |
16220 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 4 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 5 |
Correct |
4 ms |
16228 KB |
Output is correct |
| 6 |
Correct |
4 ms |
16228 KB |
Output is correct |
| 7 |
Correct |
4 ms |
16480 KB |
Output is correct |
| 8 |
Correct |
5 ms |
16232 KB |
Output is correct |
| 9 |
Correct |
5 ms |
16228 KB |
Output is correct |
| 10 |
Correct |
4 ms |
16232 KB |
Output is correct |
| 11 |
Correct |
4 ms |
16352 KB |
Output is correct |
| 12 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 13 |
Correct |
4 ms |
16052 KB |
Output is correct |
| 14 |
Correct |
4 ms |
16224 KB |
Output is correct |
| 15 |
Incorrect |
4 ms |
16220 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 4 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 5 |
Correct |
4 ms |
16228 KB |
Output is correct |
| 6 |
Correct |
4 ms |
16228 KB |
Output is correct |
| 7 |
Correct |
4 ms |
16480 KB |
Output is correct |
| 8 |
Correct |
5 ms |
16232 KB |
Output is correct |
| 9 |
Correct |
5 ms |
16228 KB |
Output is correct |
| 10 |
Execution timed out |
3059 ms |
226268 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 4 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 5 |
Correct |
4 ms |
16228 KB |
Output is correct |
| 6 |
Correct |
4 ms |
16228 KB |
Output is correct |
| 7 |
Correct |
4 ms |
16480 KB |
Output is correct |
| 8 |
Correct |
5 ms |
16232 KB |
Output is correct |
| 9 |
Correct |
5 ms |
16228 KB |
Output is correct |
| 10 |
Correct |
4 ms |
16232 KB |
Output is correct |
| 11 |
Correct |
4 ms |
16352 KB |
Output is correct |
| 12 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 13 |
Correct |
4 ms |
16052 KB |
Output is correct |
| 14 |
Correct |
4 ms |
16224 KB |
Output is correct |
| 15 |
Incorrect |
4 ms |
16220 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
