oj.uz

Submission #868858

# Submission time Handle Problem Language Result Execution time Memory
868858 2023-11-02T09:09:48 Z abcvuitunggio Keys (IOI21_keys) C++17
9 / 100
 220 ms 54548 KB 
#include <bits/stdc++.h>
using namespace std;
vector <int> ans,col[300001],ve;
vector <pair <int, int>> ke[300001];
int n,m,p[300001],d[300001],r[300001],isleaf[300001];
queue <int> q;
int f(int i){
    return (p[i]==i?i:p[i]=f(p[i]));
}
void unite(int i, int j){
    p[f(j)]=f(i);
}
int bfs(int s){
    q.push(s);
    d[s]=1;
    int res=-1;
    ve.clear();
    while (!q.empty()){
        int u=q.front();
        q.pop();
        if (f(u)!=f(s)){
            res=u;
            break;
        }
        ve.push_back(u);
        for (auto [v,c]:ke[u])
            if (!d[v])
                col[c].push_back(v);
        for (int v:col[r[u]])
            if (!d[v]){
                d[v]=1;
                q.push(v);
            }
        col[r[u]].clear();
    }
    for (int i:ve){
        d[i]=0;
        for (auto [v,c]:ke[i])
            col[c].clear();
    }
    while (!q.empty()){
        d[q.front()]=0;
        q.pop();
    }
    if (res!=-1)
        d[res]=0;
    return res;
}
vector <int> find_reachable(vector <int> R, vector <int> u, vector <int> v, vector <int> c){
    n=R.size();
    m=u.size();
    for (int i=0;i<n;i++){
        r[i]=R[i];
        p[i]=i;
        ans.push_back(0);
    }
    for (int i=0;i<m;i++){
        ke[u[i]].push_back({v[i],c[i]});
        ke[v[i]].push_back({u[i],c[i]});
    }
    bool ch=true;
    vector <pair <int, int>> tmp;
    while (ch){
        ch=false;
        tmp.clear();
        for (int i=0;i<n;i++)
            if (f(i)==i&&!isleaf[i]){
                int j=bfs(i);
                if (j==-1)
                    isleaf[i]=1;
                else{
                    tmp.push_back({j,i});
                    ch=true;
                }
            }
        for (auto [u,v]:tmp)
            unite(u,v);
    }
    int mn=1e9;
    for (int i=0;i<n;i++){
        if (i==f(i)){
            bfs(i);
            mn=min(mn,(int)ve.size());
        }
    }
    for (int i=0;i<n;i++)
        if (i==f(i)){
            bfs(i);
            if (ve.size()==mn)
                for (int j:ve)
                    ans[j]=1;
        }
	return ans;
}

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:89:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |             if (ve.size()==mn)
      |                 ~~~~~~~~~^~~~
keys.cpp:86:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   86 |     for (int i=0;i<n;i++)
      |     ^~~
keys.cpp:93:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   93 |  return ans;
      |  ^~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19052 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19052 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 4 ms 18888 KB Output is correct
12 Correct 4 ms 19036 KB Output is correct
13 Correct 4 ms 19036 KB Output is correct
14 Correct 4 ms 18876 KB Output is correct
15 Correct 4 ms 19036 KB Output is correct
16 Correct 4 ms 19036 KB Output is correct
17 Incorrect 4 ms 19052 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19052 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 4 ms 18888 KB Output is correct
12 Correct 4 ms 19036 KB Output is correct
13 Correct 4 ms 19036 KB Output is correct
14 Correct 4 ms 18876 KB Output is correct
15 Correct 4 ms 19036 KB Output is correct
16 Correct 4 ms 19036 KB Output is correct
17 Incorrect 4 ms 19052 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19052 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct
10 Correct 148 ms 41772 KB Output is correct
11 Incorrect 220 ms 54548 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19052 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 4 ms 18888 KB Output is correct
12 Correct 4 ms 19036 KB Output is correct
13 Correct 4 ms 19036 KB Output is correct
14 Correct 4 ms 18876 KB Output is correct
15 Correct 4 ms 19036 KB Output is correct
16 Correct 4 ms 19036 KB Output is correct
17 Incorrect 4 ms 19052 KB Output isn't correct
18 Halted 0 ms 0 KB -