oj.uz

Submission #872605

# Submission time Handle Problem Language Result Execution time Memory
872605 2023-11-13T12:43:28 Z lighton Keys (IOI21_keys) C++17
9 / 100
 688 ms 656072 KB 
#include<bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
using namespace std;
using pi = pair<int,int>;
struct CC{
    int grp[300001];
    int fi(int x){
        if(grp[x] == x) return x;
        else return grp[x] = fi(grp[x]);
    }
    void un(int x, int y){
        x = fi(x);
        y = fi(y);
        assert(x!=y);
        grp[x] = y;
    }
} cc;
vector<int> R,U,V,C;
struct CYCLES{
    int grp[300001];
    int siz[300001];
    int toward[300001];
    set<int> components[300001];
    set<int> colors[300001];
    map<int, queue<int> > remainedge[300001];
    queue<int> remaincolor[300001];
    int fi(int x){
        if(grp[x] == x) return x;
        else return grp[x] = fi(grp[x]);
    }
    void un(int x, int y){
        x = fi(x);
        y = fi(y);
        assert(x!=y);
        if(siz[x] > siz[y]) swap(x,y);
        siz[y] += siz[x];
        for(auto &i :components[x]){
            components[y].insert(i);
        }
        for(auto &i :colors[x]){
            if(colors[y].find(i) == colors[y].end()) {
                colors[y].insert(i);
                remaincolor[y].push(i);
            }
        }
        for(auto &i : remainedge[x]){
            if(i.second.size() && colors[y].find(i.first) != colors[y].end()) remaincolor[y].push(i.first);
            while(i.second.size()){
                remainedge[y][i.first].push(i.second.front());
                i.second.pop();
            }
        }

        grp[x] = y;
        toward[y] = -1;
    }
    void findedge(int x){
        x=fi(x);
        toward[x] = -1;
        while(remaincolor[x].size()){
            int i = remaincolor[x].front();
            while(remainedge[x][i].size()){
                int j = remainedge[x][i].front();
                remainedge[x][i].pop();
                if(components[x].find(j) == components[x].end()) toward[x] = j;
                if(toward[x] != -1) break;
            }
            if(toward[x] != -1) break;
            remaincolor[x].pop();
        }
    }
} cycles;
int N,M;
vector<pi> adj[300001];
int chk[300001];
vector<pi> candidate;
int ans = 1e9;
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	N = r.size();
    M = u.size();
    R=r;U=u;V=v;C=c;

    for(int i = 0; i<M; i++){
        adj[U[i]].push_back({V[i],C[i]});
        adj[V[i]].push_back({U[i],C[i]});
    }
    //init
    for(int i = 0; i<N; i++){
        cc.grp[i] = i;
        cycles.grp[i] = i;
    }

    for(int i = 0; i<N; i++){
        cycles.toward[i] = -1;
        cycles.components[i].insert(i);
        cycles.colors[i].insert(R[i]);
        cycles.remaincolor[i].push(R[i]);
        for(auto &j : adj[i]){
            cycles.remainedge[i][j.second].push(j.first);
            cycles.siz[i]++;
        }
        cycles.findedge(i);

        while(cycles.toward[cycles.fi(i)] != -1 && cc.fi(cycles.toward[cycles.fi(i)]) == cc.fi(i)){
            cycles.un(i,cycles.toward[cycles.fi(i)]);
            cycles.findedge(i);
        }
        if(cycles.toward[cycles.fi(i)] == -1){
            int tmp = cycles.components[cycles.fi(i)].size();
            for(int j : cycles.components[cycles.fi(i)]) candidate.push_back({j,tmp});
            ans = min(ans,tmp);
        }
        else{
            cc.un(cycles.toward[cycles.fi(i)],i);
        }
    }

    std::vector<int> ret(N, 0);
    for(auto &[i,j] : candidate){
        if(j==ans) ret[i] = 1;
    }
	return ret;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 256848 KB Output is correct
2 Correct 124 ms 256852 KB Output is correct
3 Correct 115 ms 256876 KB Output is correct
4 Correct 117 ms 257092 KB Output is correct
5 Correct 115 ms 256848 KB Output is correct
6 Correct 121 ms 257104 KB Output is correct
7 Correct 113 ms 256848 KB Output is correct
8 Correct 111 ms 256924 KB Output is correct
9 Correct 113 ms 256976 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 256848 KB Output is correct
2 Correct 124 ms 256852 KB Output is correct
3 Correct 115 ms 256876 KB Output is correct
4 Correct 117 ms 257092 KB Output is correct
5 Correct 115 ms 256848 KB Output is correct
6 Correct 121 ms 257104 KB Output is correct
7 Correct 113 ms 256848 KB Output is correct
8 Correct 111 ms 256924 KB Output is correct
9 Correct 113 ms 256976 KB Output is correct
10 Correct 115 ms 257204 KB Output is correct
11 Correct 115 ms 257108 KB Output is correct
12 Correct 114 ms 257108 KB Output is correct
13 Correct 117 ms 256772 KB Output is correct
14 Correct 113 ms 257064 KB Output is correct
15 Incorrect 117 ms 257108 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 256848 KB Output is correct
2 Correct 124 ms 256852 KB Output is correct
3 Correct 115 ms 256876 KB Output is correct
4 Correct 117 ms 257092 KB Output is correct
5 Correct 115 ms 256848 KB Output is correct
6 Correct 121 ms 257104 KB Output is correct
7 Correct 113 ms 256848 KB Output is correct
8 Correct 111 ms 256924 KB Output is correct
9 Correct 113 ms 256976 KB Output is correct
10 Correct 115 ms 257204 KB Output is correct
11 Correct 115 ms 257108 KB Output is correct
12 Correct 114 ms 257108 KB Output is correct
13 Correct 117 ms 256772 KB Output is correct
14 Correct 113 ms 257064 KB Output is correct
15 Incorrect 117 ms 257108 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 256848 KB Output is correct
2 Correct 124 ms 256852 KB Output is correct
3 Correct 115 ms 256876 KB Output is correct
4 Correct 117 ms 257092 KB Output is correct
5 Correct 115 ms 256848 KB Output is correct
6 Correct 121 ms 257104 KB Output is correct
7 Correct 113 ms 256848 KB Output is correct
8 Correct 111 ms 256924 KB Output is correct
9 Correct 113 ms 256976 KB Output is correct
10 Correct 688 ms 656072 KB Output is correct
11 Correct 664 ms 547728 KB Output is correct
12 Incorrect 257 ms 365056 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 256848 KB Output is correct
2 Correct 124 ms 256852 KB Output is correct
3 Correct 115 ms 256876 KB Output is correct
4 Correct 117 ms 257092 KB Output is correct
5 Correct 115 ms 256848 KB Output is correct
6 Correct 121 ms 257104 KB Output is correct
7 Correct 113 ms 256848 KB Output is correct
8 Correct 111 ms 256924 KB Output is correct
9 Correct 113 ms 256976 KB Output is correct
10 Correct 115 ms 257204 KB Output is correct
11 Correct 115 ms 257108 KB Output is correct
12 Correct 114 ms 257108 KB Output is correct
13 Correct 117 ms 256772 KB Output is correct
14 Correct 113 ms 257064 KB Output is correct
15 Incorrect 117 ms 257108 KB Output isn't correct
16 Halted 0 ms 0 KB -