Submission #435332

#	Time	Username	Problem	Language	Result	Execution time	Memory
435332		jangwonyoung	Keys (IOI21_keys)	C++17	100 / 100	1428 ms	84972 KiB

keys

//////////////////////////////////////////////////////
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef vector<int> vi;
const int N=3e5+1;
int n,m;
vector<pair<int,int> >adj[N];

vi alive;
bool vis[N];
bool dead[N];


int gp[N];//group of i-th dude
vector<int>oid;//out = group
int ptr=0;
//in = groups
int l[N];
int mn[N];
vector<int>rdy[N];
vector<int>mem[N];

set<pair<int,pair<int,int> > >outs2;//in = late[color] out = edge

int late[N];//late[color]=last

void upd(int sid,int id,int rid){
	for(auto c:adj[id]){
		outs2.insert({late[c.fi],{id,c.se}});
	}
	int cur=rid;
	while(true){
		auto it=outs2.lower_bound({late[cur],{0,0}});
		if(it==outs2.end() || it->fi!=late[cur]) break;
		rdy[gp[it->se.fi]].push_back(it->se.se);
		outs2.erase(it);
	}
	late[cur]=alive.size();
}
int merge(int p1,int p2){
	if(rdy[p1].size()+mem[p1].size()<rdy[p2].size()+mem[p2].size()){
		swap(p1,p2);
	}
	for(auto c:mem[p2]){
		mem[p1].push_back(c);
		gp[c]=p1;
	}
	for(auto c:rdy[p2]){
		rdy[p1].push_back(c);
	}
	mem[p2].clear();rdy[p2].clear();
	return p1;
}
int ans[N];
vi find_reachable(vi r,vi u,vi v,vi c){
	n=r.size();
	for(int i=0; i<u.size() ;i++){
		adj[u[i]].push_back({c[i],v[i]});
		adj[v[i]].push_back({c[i],u[i]});
	}
	for(int i=0; i<n ;i++) late[i]=-1-i;
	for(int i=0; i<n ;i++){
		if(!vis[i]){
			vis[i]=true;
			gp[i]=++ptr;
			mem[gp[i]].push_back(i);
			l[ptr]=0;
			mn[ptr]=alive.size();
			oid.push_back(ptr);
			upd(ptr,i,r[i]);
			alive.push_back(i);
			while(true){
				int cur=oid.back(),ly=oid.size();
                /*cout << "List " << endl;
                for(auto c:oid){
                    cout << "gp " << c << ": " << l[c] << endl;;
                    cout << "mem: ";
                    for(auto d:mem[c]){
                        cout << d << ' ';
                    }
                    cout << endl;
                    cout << "rdy: ";
                    for(auto d:rdy[c]){
                        cout << d << ' ';
                    }
                    cout << endl;
                }*/
				if(rdy[cur].empty()){//cycle end
					int cnt=0;
					for(auto c:alive){
						if(l[gp[c]]==ly-1) ++cnt;
						else ans[c]=n+1;
						dead[c]=true;
						late[r[c]]=-1-r[c];
					}
					for(auto c:alive) if(l[gp[c]]==ly-1) ans[c]=cnt;
					alive.clear();oid.clear();outs2.clear();break;
				}
				int x=rdy[cur].back();rdy[cur].pop_back();
				if(dead[x]){
					for(auto c:alive){
						dead[c]=true;
						late[r[c]]=-1-r[c];
                        ans[c]=n+1;
					}
					alive.clear();oid.clear();outs2.clear();break;
				}
				else if(!vis[x]){
					vis[x]=true;
					gp[x]=++ptr;
					mem[gp[x]].push_back(x);
					l[ptr]=ly;
					mn[ptr]=alive.size();
					oid.push_back(ptr);
					upd(ptr,x,r[x]);
					alive.push_back(x);
				}
				else{//collapse layers
					while(ly!=l[gp[x]]+1){
						ly--;
						int bad=mn[oid[ly-1]];
						while(true){
							auto it=outs2.lower_bound({bad,{0,0}});
							if(it==outs2.end()) break;
							rdy[gp[it->se.fi]].push_back(it->se.se);
							outs2.erase(it);
						}
						mn[oid[ly-1]]=min(mn[oid[ly-1]],mn[oid[ly]]);
						mn[oid[ly]]=min(mn[oid[ly-1]],mn[oid[ly]]);
						oid[ly-1]=merge(oid[ly-1],oid[ly]);
						l[oid[ly-1]]=ly-1;
						oid.pop_back();
					}
				}
			}
		}
	}
	int mn=n;
	for(int i=0; i<n ;i++) mn=min(mn,ans[i]);
	vector<int>res(n);
	for(int i=0; i<n ;i++) res[i]=(ans[i]==mn);
	return res;
}

/////////////////////////////////////////////////////

Compilation message (stderr)

keys.cpp: In function 'vi find_reachable(vi, vi, vi, vi)':
keys.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i=0; i<u.size() ;i++){
      |               ~^~~~~~~~~

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