제출 #1237642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237642		Malix	스핑크스 (IOI24_sphinx)	C++20	50 / 100	57 ms	1208 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vi p,s,brr;
int n;
vii a;

int parent(int x){
  if(p[x]==x)return x;
  return p[x]=parent(p[x]);
}

void merge(int x,int y){
  x=parent(x);
  y=parent(y);
  if(x==y)return;
  if(s[x]<s[y])swap(x,y);
  s[x]+=s[y];
  p[y]=x;
}

void dfs(int x,vi &vis){
  vis[x]=1;
  for(auto u:a[x])if(!vis[u])dfs(u,vis);
}

void solve(int l,int r,vi &arr,int sz,int x){
  if(sz==0)return;
  if(l==r){
    merge(x,arr[l]);
    return;
  }
  int m=(l+r)/2;
  vi b(n,n);
  b[x]=-1;
  REP(i,l,m+1)b[arr[i]]=-1;
  int k=perform_experiment(b);
  vi vis(n,0);
  vis[x]=1;
  REP(i,l,m+1)vis[arr[i]]=1;
  int tot=m-l+2;
  REP(j,0,n)if(!vis[j]){
    tot++;
    dfs(j,vis);
  }
  int y=tot-k;
  solve(l,m,arr,y,x);
  solve(m+1,r,arr,sz-y,x);
}

std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
  n=N;
  a.resize(n);
  REP(i,0,(int)X.size()){
    a[X[i]].PB(Y[i]);
    a[Y[i]].PB(X[i]);
  }
  p.resize(n);s.resize(n,1);
  REP(i,0,n)p[i]=i;
  vi pr(n,0);
  REP(i,0,n){
    vi dn(n,0);
    vi arr;
    for(auto u:a[i])if(pr[parent(u)]&&!dn[parent(u)]){
      dn[parent(u)]=1;
      arr.PB(u);
    }
    pr[i]=1;
    if(arr.empty())continue;
    vi b(n,n);
    for(auto u:arr)b[u]=-1;
    b[i]=-1;
    int k=perform_experiment(b);
    vi vis(n,0);
    vis[i]=1;
    for(auto u:arr)vis[u]=1;
    int tot=arr.size()+1;
    REP(j,0,n)if(!vis[j]){
      tot++;
      dfs(j,vis);
    }
    solve(0,(int)arr.size()-1,arr,tot-k,i);
  }
  vi ans(n,-1);
  int cl=0;
  REP(i,0,n)if(ans[i]==-1){
    if(ans[parent(i)]==-1)ans[parent(i)]=cl++;
    ans[i]=ans[parent(i)];
  }
  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 3
• Subtask 2: 3.5 / 7
• Subtask 3: 16.5 / 33
• Subtask 4: 10.5 / 21
• Subtask 5: 18 / 36