| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 894797 |
2023-12-29T03:38:12 Z |
Faisal_Saqib |
Keys (IOI21_keys) |
C++17 |
|
3000 ms |
1444524 KB |
#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(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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
6 ms |
16220 KB |
Output is correct |
| 4 |
Correct |
5 ms |
16400 KB |
Output is correct |
| 5 |
Correct |
4 ms |
16276 KB |
Output is correct |
| 6 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 7 |
Correct |
4 ms |
16272 KB |
Output is correct |
| 8 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 9 |
Correct |
4 ms |
16216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
6 ms |
16220 KB |
Output is correct |
| 4 |
Correct |
5 ms |
16400 KB |
Output is correct |
| 5 |
Correct |
4 ms |
16276 KB |
Output is correct |
| 6 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 7 |
Correct |
4 ms |
16272 KB |
Output is correct |
| 8 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 9 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 10 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 11 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 12 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 13 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 14 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 15 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 16 |
Correct |
3 ms |
16220 KB |
Output is correct |
| 17 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 18 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 19 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 20 |
Correct |
3 ms |
16220 KB |
Output is correct |
| 21 |
Correct |
4 ms |
16476 KB |
Output is correct |
| 22 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 23 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 24 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 25 |
Correct |
5 ms |
16472 KB |
Output is correct |
| 26 |
Correct |
5 ms |
16324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
6 ms |
16220 KB |
Output is correct |
| 4 |
Correct |
5 ms |
16400 KB |
Output is correct |
| 5 |
Correct |
4 ms |
16276 KB |
Output is correct |
| 6 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 7 |
Correct |
4 ms |
16272 KB |
Output is correct |
| 8 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 9 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 10 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 11 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 12 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 13 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 14 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 15 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 16 |
Correct |
3 ms |
16220 KB |
Output is correct |
| 17 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 18 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 19 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 20 |
Correct |
3 ms |
16220 KB |
Output is correct |
| 21 |
Correct |
4 ms |
16476 KB |
Output is correct |
| 22 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 23 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 24 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 25 |
Correct |
5 ms |
16472 KB |
Output is correct |
| 26 |
Correct |
5 ms |
16324 KB |
Output is correct |
| 27 |
Correct |
75 ms |
21588 KB |
Output is correct |
| 28 |
Correct |
59 ms |
21588 KB |
Output is correct |
| 29 |
Correct |
59 ms |
21680 KB |
Output is correct |
| 30 |
Correct |
18 ms |
18012 KB |
Output is correct |
| 31 |
Correct |
7 ms |
16220 KB |
Output is correct |
| 32 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 33 |
Correct |
7 ms |
16216 KB |
Output is correct |
| 34 |
Correct |
25 ms |
20136 KB |
Output is correct |
| 35 |
Correct |
25 ms |
19292 KB |
Output is correct |
| 36 |
Correct |
102 ms |
28408 KB |
Output is correct |
| 37 |
Correct |
101 ms |
28428 KB |
Output is correct |
| 38 |
Correct |
183 ms |
31572 KB |
Output is correct |
| 39 |
Correct |
175 ms |
31564 KB |
Output is correct |
| 40 |
Correct |
25 ms |
17236 KB |
Output is correct |
| 41 |
Correct |
35 ms |
20052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
6 ms |
16220 KB |
Output is correct |
| 4 |
Correct |
5 ms |
16400 KB |
Output is correct |
| 5 |
Correct |
4 ms |
16276 KB |
Output is correct |
| 6 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 7 |
Correct |
4 ms |
16272 KB |
Output is correct |
| 8 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 9 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 10 |
Execution timed out |
3101 ms |
1444524 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16216 KB |
Output is correct |
| 3 |
Correct |
6 ms |
16220 KB |
Output is correct |
| 4 |
Correct |
5 ms |
16400 KB |
Output is correct |
| 5 |
Correct |
4 ms |
16276 KB |
Output is correct |
| 6 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 7 |
Correct |
4 ms |
16272 KB |
Output is correct |
| 8 |
Correct |
5 ms |
16216 KB |
Output is correct |
| 9 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 10 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 11 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 12 |
Correct |
4 ms |
16216 KB |
Output is correct |
| 13 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 14 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 15 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 16 |
Correct |
3 ms |
16220 KB |
Output is correct |
| 17 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 18 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 19 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 20 |
Correct |
3 ms |
16220 KB |
Output is correct |
| 21 |
Correct |
4 ms |
16476 KB |
Output is correct |
| 22 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 23 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 24 |
Correct |
4 ms |
16220 KB |
Output is correct |
| 25 |
Correct |
5 ms |
16472 KB |
Output is correct |
| 26 |
Correct |
5 ms |
16324 KB |
Output is correct |
| 27 |
Correct |
75 ms |
21588 KB |
Output is correct |
| 28 |
Correct |
59 ms |
21588 KB |
Output is correct |
| 29 |
Correct |
59 ms |
21680 KB |
Output is correct |
| 30 |
Correct |
18 ms |
18012 KB |
Output is correct |
| 31 |
Correct |
7 ms |
16220 KB |
Output is correct |
| 32 |
Correct |
5 ms |
16220 KB |
Output is correct |
| 33 |
Correct |
7 ms |
16216 KB |
Output is correct |
| 34 |
Correct |
25 ms |
20136 KB |
Output is correct |
| 35 |
Correct |
25 ms |
19292 KB |
Output is correct |
| 36 |
Correct |
102 ms |
28408 KB |
Output is correct |
| 37 |
Correct |
101 ms |
28428 KB |
Output is correct |
| 38 |
Correct |
183 ms |
31572 KB |
Output is correct |
| 39 |
Correct |
175 ms |
31564 KB |
Output is correct |
| 40 |
Correct |
25 ms |
17236 KB |
Output is correct |
| 41 |
Correct |
35 ms |
20052 KB |
Output is correct |
| 42 |
Execution timed out |
3101 ms |
1444524 KB |
Time limit exceeded |
| 43 |
Halted |
0 ms |
0 KB |
- |
