Submission #1113742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113742		epicci23	Simurgh (IOI17_simurgh)	C++17	51 / 100	664 ms	3284 KiB

simurgh

#include "bits/stdc++.h"
#include "simurgh.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
 
const int N = 505;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct DSU{
  vector<int> par,siz;
  stack<array<int,2>> st;
  DSU(int _n){
    siz.assign(_n,1);
    par.assign(_n,0);
    iota(all(par),0);
  }
  int find(int a){
    if(par[a]==a) return a;
    return find(par[a]);
  }
  void unite(int a,int b){
    a=find(a),b=find(b);
    if(a==b) return;
    if(siz[a]>siz[b]) swap(a,b);
    st.push({a,b});
    par[a]=b;
    siz[b]+=siz[a];
  }
  void rollback(){
  	if(st.empty()) return;
  	auto x = st.top();
  	st.pop();
    par[x[0]] = x[0];
    siz[x[1]] -= siz[x[0]];
  }
};
 
vector<array<int,2>> edges;
vector<int> kader;
int n,m,tot=0;
 
bool check(int a){
  vector<int> vis(m, 0);
 
  if(kader[a] == -1) return 0;
  if(kader[a] == 1) return 1;
  if(count(all(kader),1) == n - 1) return 0;
  
  vector<int> span;
  DSU dsu(n),dsu2(n);
 
  for(int x = 0; x < m ; x++){
  	if(kader[x] != 1) continue;
  	span.push_back(x);
  	vis[x] = 1;
  	dsu.unite(edges[x][0],edges[x][1]);
  	dsu2.unite(edges[x][0],edges[x][1]);
  }
 
  if(dsu.find(edges[a][0])==dsu.find(edges[a][1])){
  	kader[a] = -1;
  	return 0;
  }

  dsu.unite(edges[a][0],edges[a][1]);
  int sil = sz(span);
  vis[a] = 1;
  span.push_back(a);
 
  for(int i = a + 1; i < m ; i++){
  	if(dsu.find(edges[i][0]) == dsu.find(edges[i][1])) continue;
  	if(kader[i] != 0) continue;
  	dsu.unite(edges[i][0],edges[i][1]);
  	dsu2.unite(edges[i][0],edges[i][1]);
  	vis[i] = 1;
    span.push_back(i);
  }
 
  int kaydet = count_common_roads(span);
  span.erase(span.begin()+sil);
 
  vector<int> same;
  same.push_back(a);
 
  for(int i = a + 1; i < m ; i++){
  	if(vis[i]) continue;
  	if(kader[i] != 0) continue;
    if(dsu2.find(edges[i][0]) == dsu2.find(edges[i][1])) continue;
    if(sz(same)+tot>=n){
      for(int U : same) kader[U] = -1;
      return 0;
    }
    dsu2.unite(edges[i][0],edges[i][1]);
    span.push_back(i);
    int kaydet2 = count_common_roads(span);
    if(kaydet2 == kaydet + 1){
    	for(int U : same) kader[U] = -1;
    	kader[i] = 1;
      tot++;
    	return 0;
    }
    else if(kaydet2 == kaydet - 1){
    	for(int U : same) kader[U] = 1;
      tot += sz(same);
    	kader[i] = -1;
    	return 1;
    }
    else same.push_back(i);
    span.pop_back();
    dsu2.rollback();
  }
   
  for(int U : same) kader[U] = 1;
  tot += sz(same);
  return 1;
}
 
vector<int> find_roads(int _n, vector<int> u, vector<int> v){
  m = sz(u), n = _n;
  kader.assign(m, 0);
  for(int i=0;i<m;i++) edges.push_back({u[i],v[i]});
  vector<int> D(m,0);
  iota(all(D),0);
  shuffle(all(D),rng);
  for(int i=0;i<m;i++) check(i);
  vector<int> ans;
  for(int i=0;i<m;i++) if(kader[i]==1) ans.push_back(i);
  return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30