Submission #1195962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195962		Amr	Keys (IOI21_keys)	C++20	9 / 100	135 ms	64904 KiB

keys

#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define sz size()
const int N = 3e5+7;
vector<ll> v1[N], v2[N];
ll vis[N];
ll p[N];
vector<ll> inside[N];
vector<pair<ll,ll> > vec;
vector<ll> myvec;
ll cnt[N];
ll tim = 1;
ll n , m;
void dfs1(ll x)
{
    if(vis[x]) return;
    vis[x] = 1;
    for(int i = 0; i < v1[x].sz; i++)
    {
        ll cur = v1[x][i];
        dfs1(cur);
    }
    vec.push_back({tim++,x});
}
void dfs2(ll x)
{
    if(vis[x]) return;
    vis[x] = 1;
    for(int i = 0; i < v2[x].sz; i++)
    {
        ll cur = v2[x][i];
        dfs2(cur);
    }
    myvec.push_back(x);
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    // std::vector<int> ans(r.size(), 1);
    n = r.sz, m = u.sz;
    for(int i = 0; i < m ;i++)
    {
        ll x = u[i], y = v[i], w = c[i];
        if(r[x]==w) {v1[x].push_back(y); v2[y].push_back(x);}
        if(r[y]==w) {v1[y].push_back(x); v2[x].push_back(y);}
    }
    for(int i = 0; i < n; i++)
    {
        if(!vis[i]) dfs1(i);
    }
    for(int i = 0; i < n; i++) vis[i] = 0;
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    for(int i = 0; i < n; i++)
    {
        ll x = vec[i].S;
        if(vis[x]) continue;
        myvec.clear();
        //continue;
        dfs2(x);
        for(int j = 0; j < myvec.sz; j++)
        {
            p[myvec[j]] = x;
            inside[x].push_back(myvec[j]);
        }
        p[x] = x;
       //cout << x << "  "; for(int i = 0; i < myvec.sz; i++) cout << myvec[i] << " "; cout << endl;
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < v1[i].sz; j++)
        {
            ll x = i , y = v1[i][j];
            if(p[x]==p[y]) continue;
            cnt[p[x]]++;
        }
    }
    ll mn = 1e9;
    vector<int> ans(n,0);
    for(int i = 0; i < n; i++)
    {
        if(p[i]!=i) continue;
        if(cnt[i]!=0) continue;
        mn = min(mn,(ll) inside[i].sz+1);
    }
    for(int i = 0; i < n; i++)
    {
        if(p[i]==i&&cnt[i]==0&&inside[i].sz+1==mn)
        {
            for(int j  = 0; j < inside[i].sz; j++) ans[inside[i][j]] = 1;
        }
    }
    return ans;
}

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