Submission #1062102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062102		new_acc	Keys (IOI21_keys)	C++17	100 / 100	1256 ms	146284 KiB

keys

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=3e5+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],n,fau[N],m;
bool ok[N],vis[N],vis2[N];
vi kt[N],dk[N],curr;
vector<pair<int,int> >graf[N];
set<int> dos[N];
set<pair<int,int>> zab[N];
void Union(int a,int b){
    a=fau[a],b=fau[b];
    if(a==b) return;
    if(kt[a].size()>kt[b].size()) swap(a,b);
    for(auto v:kt[a]) dos[b].insert(t[v]),fau[v]=b;
    dos[a].clear(),zab[a].clear();
    ok[b]&=ok[a];
    for(auto v:kt[a]){
        kt[b].push_back(v);
        for(auto [u,c]:graf[v]){
            auto it=dos[b].lower_bound(c);
            if(it!=dos[b].end() and (*it)==c){
                dk[b].push_back(u); 
            }else zab[b].insert({c,u});
        }
        auto it=zab[b].lower_bound({t[v],0});
        while(it!=zab[b].end() and (*it).fi==t[v]){
            dk[b].push_back((*it).se);
            zab[b].erase(it);
            it=zab[b].lower_bound({t[v],0});
        }
    }
    kt[a].clear();
}
void dfs(int v){
    vis[v]=1;
    vis2[v]=1;
    curr.push_back(v);
    while(dk[fau[v]].size()){
        int u=dk[fau[v]].back();
        dk[fau[v]].pop_back();
        if(vis[u] and !vis2[u]){
            ok[fau[v]]=0;
            continue;
        }
        if(vis[u]){
            while(curr.size() and fau[curr.back()]!=fau[u]){
                Union(u,curr.back());
                curr.pop_back();
            }     
        }else{
            dfs(u);
            if(fau[v]!=fau[u]) ok[fau[v]]=0;
        }
    }
    if(curr.size() and curr.back()==v)
        curr.pop_back();
    vis2[v]=0;
}
vi find_reachable(vi pom1,vi pom2,vi pom3,vi pom4){
    int n=pom1.size(),m=pom2.size();
    iota(fau,fau+1+n,0);
    for(int i=1;i<=n;i++){
        t[i]=pom1[i-1];
        t[i]++;
        ok[i]=1;
        dos[i].insert(t[i]);
        kt[i].push_back(i);
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        a=pom2[i-1],b=pom3[i-1],c=pom4[i-1];
        c++,a++,b++;
        graf[a].push_back({b,c}),graf[b].push_back({a,c});
        if(c==t[a]) dk[a].push_back(b);
        else zab[a].insert({c,b});
        if(c==t[b]) dk[b].push_back(a);
        else zab[b].insert({c,a});
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]) dfs(i);
    }
    int mini=INFi;
    for(int i=1;i<=n;i++){
        if(ok[fau[i]])
            mini=min(mini,(int)kt[fau[i]].size());
    }
    vi res;
    for(int i=1;i<=n;i++){
        if(!ok[fau[i]] or mini<kt[fau[i]].size()) res.push_back(0);
        else res.push_back(1);
    }
    return res;
}

Compilation message (stderr)

keys.cpp: In function 'vi find_reachable(vi, vi, vi, vi)':
keys.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         if(!ok[fau[i]] or mini<kt[fau[i]].size()) res.push_back(0);
      |                           ~~~~^~~~~~~~~~~~~~~~~~

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