| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 873469 |
2023-11-15T06:47:54 Z |
1bin |
열쇠 (IOI21_keys) |
C++17 |
|
17 ms |
52316 KB |
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 3e5 + 505, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans,k;
//shfit + tab
//ctrl + k + c
ll gcd(ll x, ll y) {
if (!y)return x;
return gcd(y, x % y);
};
ll par[n_],to[n_],par2[n_],sz[n_],Y[n_];
vector<P>v[n_];
set<ll>key[n_];
vector<ll>go[n_];
//현재 가지고 있는 키들의 종류
vector<vector<ll>>prohibit;
map<ll,ll>mp[n_];
//갈 수 있는 곳s
ll find(ll x){
if(par[x]<0)return x;
return par[x]=find(par[x]);
}
ll find2(ll x){
if(par2[x]<0)return x;
return par2[x]=find(par2[x]);
}
void merge2(ll x,ll y){
x=find2(x),y=find2(y);
if(x==y)return;
par2[x]=y;
}
void chk(ll x){
x=find(x);
while(go[x].size() && find(x)==find(go[x].back())){
go[x].pop_back();
}
}
void merge(ll x,ll y){
x=find(x),y=find(y);
if(x==y)return;
//x is always larger than y
//
//if(key[x].size()<key[y].size())swap(x,y);
for(auto nxt:key[y]){
if(key[x].find(nxt)==key[x].end()){
//새로운 key가 들어 왔을 경우
key[x].insert(nxt);
if(mp[x].find(nxt)!=mp[x].end()){
int idx=mp[x][nxt];
for(auto i:prohibit[idx])go[x].push_back(i);
prohibit[idx].clear();
mp[x].erase(nxt);
}
}
}
for(auto nxt:mp[y]){
if(key[x].find(nxt.first)==key[x].end()){
if(mp[x].find(nxt.first)!=mp[x].end()){
int idx1=mp[x][nxt.first],idx2=nxt.second;
for(auto i:prohibit[idx2])prohibit[idx1].push_back(i);
prohibit[idx2].clear();
}
else{
mp[x][nxt.first]=nxt.second;
}
}
else{
for(auto i:prohibit[nxt.second])go[x].push_back(i);
prohibit[nxt.second].clear();
}
}
for(auto nxt:go[y])go[x].push_back(nxt);
mp[y].clear(),go[y].clear();
par[y]=x;
sz[x]+=sz[y];
chk(x);
}
void add_edge(int a, int b, int c){
vector<ll> tmp;
if(mp[a].find(c) == mp[a].end()){
prohibit.push_back(tmp);
prohibit[base].push_back(b);
mp[a][c] = base++;
}
else prohibit[mp[a][c]].push_back(b);
return;
}
vector<int> find_reachable(vector<int>R,vector<int>U,vector<int>V,vector<int>C){
n=R.size(); m=U.size();
vector<int>ret(n);
memset(par,-1,sizeof(par));
memset(par2,-1,sizeof(par2));
fill(sz,sz+n_,1);
for(int i=0;i<m;i++){
a=U[i],b=V[i],c=C[i];
add_edge(a, b, c);
add_edge(b, a, c);
}
vector<ll>flag;
for(int i=0;i<n;i++){
key[i].insert(R[i]);
if(!mp[i][R[i]]){
flag.push_back(i);
continue;
}
ll index=mp[i][R[i]];
for(auto nxt:prohibit[index])go[i].push_back(nxt);
prohibit[index].clear();
mp[i].erase(R[i]);
}
if(flag.size()){
for(auto nxt:flag)ret[nxt]=1;
return ret;
}
// subtask 1
// R[i]가 모두 0인 경우만 살아남음
for(int i = 0; i < n; i++) assert(R[i] == 0);
//assert(0);
//이 케이스는 도착가능한 정점이 자기자신 뿐인 정점이 존재해서, 그 정점이 정답이 될 때.
//그것이 아니라면 functional graph이기 때문에 scc가 연결 그래프 당 정확히 1개 존재해서 그 정점들을 묶을 수 있다.
queue<ll>q;
vector<int>indegree(n),checked(n),cycle;
for(int i=0;i<n;i++){
assert(go[i].size());
merge2(i,go[i].back());
indegree[go[i].back()]++;
}
for(int i=0;i<n;i++){
if(indegree[i])continue;
checked[i]=true;
q.push(i);
}
while(q.size()){
x=q.front(); q.pop();
int nx=go[x].back();
if(--indegree[nx]==0){
q.push(nx);
checked[nx]=true;
}
}
for(int i=0;i<n;i++){
if(checked[i])continue;
cycle.push_back(i);
}
ans=inf;
vector<ll>root;
for(auto x:cycle){
if(checked[x])continue;
vector<ll>T;
T.push_back(x);
checked[x]=true;
int y = go[x].back();
while(!checked[y]){
T.push_back(y);
checked[y]=true;
y= go[y].back();
}
assert(x==y);
ll tmp=T[0];
for(auto nxt:T) merge(tmp,nxt);
root.push_back(find(x));
}
while(root.size()){
a=root.back(); root.pop_back();
if(go[a].size()){
if(find2(a)==find2(go[a].back())){
vector<ll>T;
T.push_back(a);
ll now=find(go[a].back());
while(1){
T.push_back(now);
now=find(go[now].back());
if(a==now)break;
}
for(auto nxt:T)merge(a,nxt);
root.push_back(find(a));
}
else{
merge2(a,go[a].back());
}
}
else{
Y[a] = 1;
ans=min(ans,sz[a]);
}
}
assert(ans < inf);
for(int i=0;i<n;i++){
if(!Y[find(i)] || sz[find(i)]!=ans)continue;
ret[i]=1;
}
return ret;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
52316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
52316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
52316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
52316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
52316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
