Submission #868659

#	Time	Username	Problem	Language	Result	Execution time	Memory
868659		abcvuitunggio	Keys (IOI21_keys)	C++17	9 / 100	124 ms	39652 KiB

keys

#include <bits/stdc++.h>
using namespace std;
vector <int> ke[300001],res;
int n,m,isInStack[300001],low[300001],idx[300001],R[300001],cnt[300001],ch[300001],id=1,mn=1e9;
stack <int> s;
void ssc(int v){
    idx[v]=id;
    low[v]=id;
    id++;
    s.push(v);
    isInStack[v]=1;
    for (int w:ke[v]){
        if (idx[w]==0){
            ssc(w);
            low[v]=min(low[w],low[v]);
        }
        else if (isInStack[w])
            low[v]=min(low[v],idx[w]);
    }
    if (low[v]==idx[v]){
        while (s.top()!=v){
            isInStack[s.top()]=false;
            R[s.top()]=v;
            cnt[v]++;
            s.pop();
        }
        isInStack[v]=false;
        cnt[v]++;
        s.pop();
    }
}
void tarjan(){
    iota(R,R+n,0);
    for (int i=0;i<n;i++)
        if (idx[i]==0)
            ssc(i);
}
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<m;i++){
        if (r[u[i]]==c[i])
            ke[u[i]].push_back(v[i]);
        if (r[v[i]]==c[i])
            ke[v[i]].push_back(u[i]);
    }
    tarjan();
    for (int i=0;i<n;i++)
        for (int j:ke[i])
            if (R[j]!=R[i])
                ch[R[i]]=1;
    for (int i=0;i<n;i++)
        if (i==R[i]&&!ch[i])
            mn=min(mn,cnt[i]);
    for (int i=0;i<n;i++)
        res.push_back(!ch[R[i]]&&cnt[R[i]]==mn);
	return res;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:55:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   55 |     for (int i=0;i<n;i++)
      |     ^~~
keys.cpp:57:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   57 |  return res;
      |  ^~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33