Submission #1037184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037184		huutuan	Simurgh (IOI17_simurgh)	C++14	0 / 100	0 ms	344 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>

using namespace std;

struct DSU{
   vector<int> lab;
   void init(int n){
      lab.assign(n, -1);
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   bool union_sets(int u, int v){
      u=find_set(u); v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         lab[u]+=lab[v];
         lab[v]=u;
         return 1;
      }
      return 0;
   }
};

const int N=510;
vector<int> g[N], gg[N];
pair<int, int> edge[N*N];
int n, m, dep[N], par[N], val[N], vis[N];

void dfs(int u, int p){
   par[u]=p;
   for (int i:g[u]) if (i!=p){
      int v=edge[i].first^edge[i].second^u;
      if (dep[v]!=-1){
         if (dep[v]>dep[u]) gg[v].push_back(i);
      }else{
         dep[v]=dep[u]+1;
         dfs(v, i);
      }
   }
}

vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
   n=_n, m=_u.size();
   for (int i=0; i<m; ++i){
      g[_u[i]].push_back(i);
      g[_v[i]].push_back(i);
      edge[i]={_u[i], _v[i]};
   }
   memset(dep, -1, sizeof dep);
   memset(val, -1, sizeof val);
   dep[0]=0;
   dfs(0, -1);
   for (int v=1; v<n; ++v){
      for (int i:gg[v]){
         memset(vis, 0, sizeof vis);
         int u=edge[i].first^edge[i].second^v;
         vector<int> v1, v2{i}, need, cycle{u};
         int x=-1;
         {
            int w=v;
            while (w!=u){
               cycle.push_back(w);
               v2.push_back(par[w]);
               vis[w]=1;
               if (val[w]==-1){
                  need.push_back(w);
               }else{
                  x=w;
               }
               w=edge[par[w]].first^edge[par[w]].second^w;
            }
         }
         for (int j=1; j<n; ++j) if (!vis[j]) v1.push_back(par[j]);
         if (need.empty()) continue;
         auto query=[&](int t){
            vector<int> vv=v1;
            for (int j:v2) if (j!=t) vv.push_back(j);
            return count_common_roads(vv);
         };
         if (x==-1){
            vector<int> vals;
            for (int i:v2){
               vals.push_back(query(i));
            }
            int all=*max_element(vals.begin(), vals.end());
            for (int i=1; i<(int)v2.size(); ++i) val[cycle[i]]=all-vals[i];
         }else{
            int all=query(par[x])+val[x];
            for (int w:need) val[w]=all-query(par[w]);
         }
      }
   }
   for (int i=1; i<n; ++i) if (val[i]==-1) val[i]=1;
   vector<int> ans;
   for (int u=0; u<n; ++u){
      vector<int> tmp; tmp.swap(g[u]);
      for (int v:tmp) if (u<v) g[u].push_back(v);
      auto query=[&](int l, int r){
         DSU dsu; dsu.init(n);
         vector<int> vv;
         for (int i=l; i<=r; ++i){
            dsu.union_sets(edge[g[u][i]].first, edge[g[u][i]].second);
            vv.push_back(g[u][i]);
         }
         int cnt=0;
         for (int i=1; i<n; ++i) if (dsu.union_sets(edge[par[i]].first, edge[par[i]].second)){
            vv.push_back(par[i]);
            cnt+=val[i];
         }
         return count_common_roads(vv)-cnt;
      };
      int t=0, cnt=query(0, (int)g[u].size()-1);
      while (cnt--){
         int l=t, r=(int)g[u].size()-1;
         while (l<=r){
            int mid=(l+r)>>1;
            if (query(l, mid)) r=mid-1;
            else l=mid+1;
         }
         ans.push_back(g[u][l]);
         t=l+1;
      }
   }
   return ans;
}

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