Submission #1025561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025561		huutuan	Simurgh (IOI17_simurgh)	C++14	51 / 100	149 ms	2908 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 check(int u, int v){
      return find_set(u)==find_set(v);
   }
   void 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;
      }
   }
};

int query(vector<int> &v, int x){
   v.push_back(x);
   int ans=count_common_roads(v);
   v.pop_back();
   return ans;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
   int m=u.size();
   int cnt=0;
   vector<int> check(m, -1);
   for (int i=0; i<m; ++i) if (check[i]==-1){
      DSU dsu1, dsu2;
      dsu1.init(n); dsu2.init(n);
      vector<int> id;
      dsu1.union_sets(u[i], v[i]);
      for (int j=0; j<m; ++j) if (i!=j){
         if (!dsu1.check(u[j], v[j])){
            dsu1.union_sets(u[j], v[j]);
            dsu2.union_sets(u[j], v[j]);
            id.push_back(j);
         }
      }
      int val=query(id, i);
      int val0=-1;
      for (int j=0; j<m; ++j) if (i!=j){
         if (!dsu2.check(u[j], v[j])){
            if (check[j]!=-1 && val0==-1){
               val0=query(id, j)-check[j];
            }
         }
      }
      if (val0!=-1){
         check[i]=val-val0;
         for (int j=0; j<m; ++j) if (i!=j){
            if (!dsu2.check(u[j], v[j])){
               if (check[j]==-1){
                  check[j]=query(id, j)-val0;
               }
            }
         }
      }else{
         val0=val;
         vector<int> vv(m);
         for (int j=0; j<m; ++j) if (i!=j){
            if (!dsu2.check(u[j], v[j])){
               vv[j]=query(id, j);
               val0=max(val0, vv[j]);
            }
         }
         --val0;
         check[i]=val-val0;
         for (int j=0; j<m; ++j) if (i!=j){
            if (!dsu2.check(u[j], v[j])){
               check[j]=vv[j]-val0;
            }
         }
      }
   }
   vector<int> ans;
   for (int i=0; i<m; ++i) if (check[i]) ans.push_back(i);
   return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:37:8: warning: unused variable 'cnt' [-Wunused-variable]
   37 |    int cnt=0;
      |        ^~~

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