# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
621140 |
2022-08-03T12:52:04 Z |
MKopchev |
Keys (IOI21_keys) |
C++17 |
|
2260 ms |
85064 KB |
#include "keys.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=3e5+42;
vector< pair<int,int> > adj[nmax];
set<int> in[nmax];
int parent[nmax];
int root(int node)
{
if(parent[node]==node)return node;
parent[node]=root(parent[node]);
return parent[node];
}
stack<int> st;
bool been[nmax];
void dfs(int node)
{
if(been[node])return;
been[node]=1;
for(auto w:adj[node])
if(in[root(node)].count(w.second))
{
dfs(w.first);
}
st.push(node);
}
vector<int> component={};
void dfs_trav(int node)
{
if(been[node])return;
been[node]=1;
component.push_back(node);
for(auto w:adj[node])
if(in[root(w.first)].count(w.second))
{
dfs_trav(w.first);
}
}
void my_merge(int u,int v)
{
u=root(u);
v=root(v);
if(u==v)return;
if(in[u].size()<in[v].size())swap(u,v);
for(auto w:in[v])
in[u].insert(w);
parent[v]=u;
}
int cnt[nmax];
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();
for(int i=0;i<n;i++)
{
parent[i]=i;
in[i].insert(r[i]);
}
int m=u.size();
for(int j=0;j<m;j++)
{
adj[u[j]].push_back({v[j],c[j]});
adj[v[j]].push_back({u[j],c[j]});
}
for(int t=0;t<5;t++)
{
for(int p=0;p<n;p++)
been[p]=0;
for(int i=0;i<n;i++)
if(been[i]==0)
dfs(i);
for(int p=0;p<n;p++)
been[p]=0;
while(st.size())
{
component={};
int tp=st.top();
st.pop();
dfs_trav(tp);
/*
cout<<tp<<" ";
cout<<"component: ";for(auto w:component)cout<<w<<" ";cout<<endl;
*/
for(int j=1;j<component.size();j++)
my_merge(component[j-1],component[j]);
}
/*
for(int j=0;j<n;j++)
cout<<root(j)<<" ";cout<<endl;
*/
}
for(int i=0;i<n;i++)
{
//cout<<i<<" -> "<<root(i)<<endl;
cnt[root(i)]++;
}
for(int j=0;j<m;j++)
{
if(root(u[j])!=root(v[j]))
{
if(in[root(u[j])].count(c[j]))cnt[root(u[j])]=0;
if(in[root(v[j])].count(c[j]))cnt[root(v[j])]=0;
}
}
int MINI=1e9;
for(int i=0;i<n;i++)
if(cnt[i])MINI=min(MINI,cnt[i]);
vector<int> outp(r.size(),0);
for(int i=0;i<n;i++)
if(cnt[root(i)]==MINI)outp[i]=1;
return outp;
}
/*
int main() {
int n, m;
assert(2 == scanf("%d%d", &n, &m));
std::vector<int> r(n), u(m), v(m), c(m);
for(int i=0; i<n; i++) {
assert(1 == scanf("%d", &r[i]));
}
for(int i=0; i<m; i++) {
assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
}
fclose(stdin);
std::vector<int> ans = find_reachable(r, u, v, c);
for (int i = 0; i < (int) ans.size(); ++i) {
if(i) putchar(' ');
putchar(ans[i]+'0');
}
printf("\n");
return 0;
}
*/
Compilation message
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:121:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int j=1;j<component.size();j++)
| ~^~~~~~~~~~~~~~~~~
keys.cpp:154:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
154 | for(int i=0;i<n;i++)
| ^~~
keys.cpp:157:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
157 | return outp;
| ^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
21460 KB |
Output is correct |
2 |
Correct |
10 ms |
21332 KB |
Output is correct |
3 |
Correct |
11 ms |
21332 KB |
Output is correct |
4 |
Correct |
12 ms |
21460 KB |
Output is correct |
5 |
Correct |
11 ms |
21340 KB |
Output is correct |
6 |
Correct |
11 ms |
21460 KB |
Output is correct |
7 |
Correct |
11 ms |
21332 KB |
Output is correct |
8 |
Correct |
11 ms |
21464 KB |
Output is correct |
9 |
Correct |
11 ms |
21396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
21460 KB |
Output is correct |
2 |
Correct |
10 ms |
21332 KB |
Output is correct |
3 |
Correct |
11 ms |
21332 KB |
Output is correct |
4 |
Correct |
12 ms |
21460 KB |
Output is correct |
5 |
Correct |
11 ms |
21340 KB |
Output is correct |
6 |
Correct |
11 ms |
21460 KB |
Output is correct |
7 |
Correct |
11 ms |
21332 KB |
Output is correct |
8 |
Correct |
11 ms |
21464 KB |
Output is correct |
9 |
Correct |
11 ms |
21396 KB |
Output is correct |
10 |
Correct |
10 ms |
21460 KB |
Output is correct |
11 |
Correct |
10 ms |
21460 KB |
Output is correct |
12 |
Correct |
10 ms |
21488 KB |
Output is correct |
13 |
Correct |
11 ms |
21460 KB |
Output is correct |
14 |
Correct |
12 ms |
21436 KB |
Output is correct |
15 |
Correct |
10 ms |
21460 KB |
Output is correct |
16 |
Correct |
11 ms |
21448 KB |
Output is correct |
17 |
Correct |
11 ms |
21456 KB |
Output is correct |
18 |
Correct |
11 ms |
21460 KB |
Output is correct |
19 |
Correct |
11 ms |
21332 KB |
Output is correct |
20 |
Correct |
11 ms |
21460 KB |
Output is correct |
21 |
Correct |
10 ms |
21460 KB |
Output is correct |
22 |
Correct |
11 ms |
21460 KB |
Output is correct |
23 |
Correct |
10 ms |
21460 KB |
Output is correct |
24 |
Correct |
12 ms |
21460 KB |
Output is correct |
25 |
Correct |
13 ms |
21412 KB |
Output is correct |
26 |
Correct |
11 ms |
21488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
21460 KB |
Output is correct |
2 |
Correct |
10 ms |
21332 KB |
Output is correct |
3 |
Correct |
11 ms |
21332 KB |
Output is correct |
4 |
Correct |
12 ms |
21460 KB |
Output is correct |
5 |
Correct |
11 ms |
21340 KB |
Output is correct |
6 |
Correct |
11 ms |
21460 KB |
Output is correct |
7 |
Correct |
11 ms |
21332 KB |
Output is correct |
8 |
Correct |
11 ms |
21464 KB |
Output is correct |
9 |
Correct |
11 ms |
21396 KB |
Output is correct |
10 |
Correct |
10 ms |
21460 KB |
Output is correct |
11 |
Correct |
10 ms |
21460 KB |
Output is correct |
12 |
Correct |
10 ms |
21488 KB |
Output is correct |
13 |
Correct |
11 ms |
21460 KB |
Output is correct |
14 |
Correct |
12 ms |
21436 KB |
Output is correct |
15 |
Correct |
10 ms |
21460 KB |
Output is correct |
16 |
Correct |
11 ms |
21448 KB |
Output is correct |
17 |
Correct |
11 ms |
21456 KB |
Output is correct |
18 |
Correct |
11 ms |
21460 KB |
Output is correct |
19 |
Correct |
11 ms |
21332 KB |
Output is correct |
20 |
Correct |
11 ms |
21460 KB |
Output is correct |
21 |
Correct |
10 ms |
21460 KB |
Output is correct |
22 |
Correct |
11 ms |
21460 KB |
Output is correct |
23 |
Correct |
10 ms |
21460 KB |
Output is correct |
24 |
Correct |
12 ms |
21460 KB |
Output is correct |
25 |
Correct |
13 ms |
21412 KB |
Output is correct |
26 |
Correct |
11 ms |
21488 KB |
Output is correct |
27 |
Correct |
12 ms |
21716 KB |
Output is correct |
28 |
Correct |
12 ms |
21640 KB |
Output is correct |
29 |
Correct |
12 ms |
21648 KB |
Output is correct |
30 |
Correct |
12 ms |
21588 KB |
Output is correct |
31 |
Correct |
11 ms |
21588 KB |
Output is correct |
32 |
Correct |
11 ms |
21460 KB |
Output is correct |
33 |
Correct |
12 ms |
21588 KB |
Output is correct |
34 |
Correct |
12 ms |
21588 KB |
Output is correct |
35 |
Correct |
12 ms |
21588 KB |
Output is correct |
36 |
Correct |
15 ms |
21844 KB |
Output is correct |
37 |
Correct |
14 ms |
21844 KB |
Output is correct |
38 |
Correct |
17 ms |
21868 KB |
Output is correct |
39 |
Correct |
16 ms |
21940 KB |
Output is correct |
40 |
Correct |
15 ms |
21596 KB |
Output is correct |
41 |
Correct |
14 ms |
21588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
21460 KB |
Output is correct |
2 |
Correct |
10 ms |
21332 KB |
Output is correct |
3 |
Correct |
11 ms |
21332 KB |
Output is correct |
4 |
Correct |
12 ms |
21460 KB |
Output is correct |
5 |
Correct |
11 ms |
21340 KB |
Output is correct |
6 |
Correct |
11 ms |
21460 KB |
Output is correct |
7 |
Correct |
11 ms |
21332 KB |
Output is correct |
8 |
Correct |
11 ms |
21464 KB |
Output is correct |
9 |
Correct |
11 ms |
21396 KB |
Output is correct |
10 |
Correct |
492 ms |
47284 KB |
Output is correct |
11 |
Correct |
585 ms |
63176 KB |
Output is correct |
12 |
Correct |
101 ms |
30032 KB |
Output is correct |
13 |
Correct |
580 ms |
63688 KB |
Output is correct |
14 |
Correct |
298 ms |
82972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
21460 KB |
Output is correct |
2 |
Correct |
10 ms |
21332 KB |
Output is correct |
3 |
Correct |
11 ms |
21332 KB |
Output is correct |
4 |
Correct |
12 ms |
21460 KB |
Output is correct |
5 |
Correct |
11 ms |
21340 KB |
Output is correct |
6 |
Correct |
11 ms |
21460 KB |
Output is correct |
7 |
Correct |
11 ms |
21332 KB |
Output is correct |
8 |
Correct |
11 ms |
21464 KB |
Output is correct |
9 |
Correct |
11 ms |
21396 KB |
Output is correct |
10 |
Correct |
10 ms |
21460 KB |
Output is correct |
11 |
Correct |
10 ms |
21460 KB |
Output is correct |
12 |
Correct |
10 ms |
21488 KB |
Output is correct |
13 |
Correct |
11 ms |
21460 KB |
Output is correct |
14 |
Correct |
12 ms |
21436 KB |
Output is correct |
15 |
Correct |
10 ms |
21460 KB |
Output is correct |
16 |
Correct |
11 ms |
21448 KB |
Output is correct |
17 |
Correct |
11 ms |
21456 KB |
Output is correct |
18 |
Correct |
11 ms |
21460 KB |
Output is correct |
19 |
Correct |
11 ms |
21332 KB |
Output is correct |
20 |
Correct |
11 ms |
21460 KB |
Output is correct |
21 |
Correct |
10 ms |
21460 KB |
Output is correct |
22 |
Correct |
11 ms |
21460 KB |
Output is correct |
23 |
Correct |
10 ms |
21460 KB |
Output is correct |
24 |
Correct |
12 ms |
21460 KB |
Output is correct |
25 |
Correct |
13 ms |
21412 KB |
Output is correct |
26 |
Correct |
11 ms |
21488 KB |
Output is correct |
27 |
Correct |
12 ms |
21716 KB |
Output is correct |
28 |
Correct |
12 ms |
21640 KB |
Output is correct |
29 |
Correct |
12 ms |
21648 KB |
Output is correct |
30 |
Correct |
12 ms |
21588 KB |
Output is correct |
31 |
Correct |
11 ms |
21588 KB |
Output is correct |
32 |
Correct |
11 ms |
21460 KB |
Output is correct |
33 |
Correct |
12 ms |
21588 KB |
Output is correct |
34 |
Correct |
12 ms |
21588 KB |
Output is correct |
35 |
Correct |
12 ms |
21588 KB |
Output is correct |
36 |
Correct |
15 ms |
21844 KB |
Output is correct |
37 |
Correct |
14 ms |
21844 KB |
Output is correct |
38 |
Correct |
17 ms |
21868 KB |
Output is correct |
39 |
Correct |
16 ms |
21940 KB |
Output is correct |
40 |
Correct |
15 ms |
21596 KB |
Output is correct |
41 |
Correct |
14 ms |
21588 KB |
Output is correct |
42 |
Correct |
492 ms |
47284 KB |
Output is correct |
43 |
Correct |
585 ms |
63176 KB |
Output is correct |
44 |
Correct |
101 ms |
30032 KB |
Output is correct |
45 |
Correct |
580 ms |
63688 KB |
Output is correct |
46 |
Correct |
298 ms |
82972 KB |
Output is correct |
47 |
Correct |
10 ms |
21460 KB |
Output is correct |
48 |
Correct |
10 ms |
21332 KB |
Output is correct |
49 |
Correct |
10 ms |
21444 KB |
Output is correct |
50 |
Correct |
247 ms |
72984 KB |
Output is correct |
51 |
Correct |
265 ms |
71804 KB |
Output is correct |
52 |
Correct |
485 ms |
49188 KB |
Output is correct |
53 |
Correct |
531 ms |
49292 KB |
Output is correct |
54 |
Correct |
492 ms |
49152 KB |
Output is correct |
55 |
Correct |
445 ms |
48764 KB |
Output is correct |
56 |
Correct |
816 ms |
65484 KB |
Output is correct |
57 |
Correct |
440 ms |
61632 KB |
Output is correct |
58 |
Correct |
445 ms |
61788 KB |
Output is correct |
59 |
Correct |
2064 ms |
65708 KB |
Output is correct |
60 |
Correct |
2185 ms |
79696 KB |
Output is correct |
61 |
Correct |
2260 ms |
79668 KB |
Output is correct |
62 |
Correct |
728 ms |
62980 KB |
Output is correct |
63 |
Correct |
240 ms |
61160 KB |
Output is correct |
64 |
Correct |
15 ms |
22516 KB |
Output is correct |
65 |
Correct |
15 ms |
22484 KB |
Output is correct |
66 |
Correct |
779 ms |
62976 KB |
Output is correct |
67 |
Correct |
39 ms |
28108 KB |
Output is correct |
68 |
Correct |
70 ms |
32660 KB |
Output is correct |
69 |
Correct |
2032 ms |
65652 KB |
Output is correct |
70 |
Correct |
111 ms |
44032 KB |
Output is correct |
71 |
Correct |
357 ms |
85064 KB |
Output is correct |
72 |
Correct |
1845 ms |
67588 KB |
Output is correct |
73 |
Correct |
750 ms |
63012 KB |
Output is correct |