Submission #1051193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051193		boyliguanhan	Simurgh (IOI17_simurgh)	C++17	100 / 100	61 ms	6716 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
#define Z 510
using namespace std;
vector<int>R;
int N_,K_;
int indexofr[Z][Z],deg[Z],royaltree[Z],parind[Z],acpar[Z],dep[Z];
vector<pair<int,int>>tre;
vector<int>U,V;
vector<int>AADJ[Z],bak[Z];
bitset<Z>vis,col,don;
void assert2(int k){
    if(!k){
        vector<int>v;
        for(int i=0;;i++)
            v.push_back(i);
    }
}
void AD(int x,int y){
    R.push_back(indexofr[x][y]-1);
}
int Q(){
    return count_common_roads(R);
}
int Q(vector<int>v){
    for(auto&i:v)i--;
    return count_common_roads(v);
}
struct dsu{
    int par[501];
    int abp(int n){
        return par[n]?par[n]=abp(par[n]):n;
    }
    bool merge(int a,int b){
        a=abp(a+1),b=abp(b+1);
        if(a==b) return 0;
        return par[a]=b;
    }
    void reset(){
        memset(par,0,sizeof par);
    }
} tis, TIS2;
vector<int>path{-1};
void calcfortree(int n){
    path.push_back(n);
    for(auto i:AADJ[n])
        if(acpar[i]==n)
            calcfortree(i);
    int d=1e9;
    for(auto i:AADJ[n])
        d=min(d,dep[i]);
    if(d<dep[n]-1){
        vector<int>V;
        int D=indexofr[n][path[d]];
        for(auto[x,y]:tre)
            V.push_back(indexofr[x][y]);
        V.push_back(D);
        vector<int>undet,det,path2=path;
        path.pop_back();
        while(path2.size()>d+1) {
            if(don[parind[path2.back()]])
                det.push_back(path2.back());
            else undet.push_back(path2.back()),
                col[parind[path2.back()]]=0;
            don[parind[path2.back()]]=1;path2.pop_back();
        }
        if(undet.empty()) return;
        if(det.empty()){
            map<int,vector<int>>mp;
            for(auto i:undet) {
                int RD=indexofr[i][acpar[i]];
                V.erase(find(V.begin(),V.end(),RD));
                mp[Q(V)].push_back(i);
                V.push_back(RD);
            }
            V.erase(find(V.begin(),V.end(),D));
            mp[Q(V)].push_back(N_);
            V.push_back(D);
            if(mp.size()==2)
                for(auto i:mp.begin()->second)
                    if(i<N_) col[parind[i]]=1;
        } else {
            int rk=det[0];
            int RD=indexofr[rk][acpar[rk]];
            V.erase(find(V.begin(),V.end(),RD));
            int akt=Q(V)+col[parind[rk]];
            V.push_back(RD);
            for(auto i:undet){
                RD=indexofr[i][acpar[i]];
                V.erase(find(V.begin(),V.end(),RD));
                col[parind[i]]=akt!=Q(V);
                V.push_back(RD);
            }
        }
    } else path.pop_back();
}
void gendfstree(int n,int p){
    vis[n]=1,dep[n]=dep[p]+1;
    for(auto i:AADJ[n]){
        if(i==p)continue;
        if(!vis[i]) acpar[i]=n,
            parind[i]=tre.size(),
            tre.push_back({n,i}),
            gendfstree(i,n);
    }
    if(!n)calcfortree(n);
}
vector<int>ans;
int countst(vector<int> x,int pivot){
    R.clear();
    tis.reset();
    for(auto i:x)AD(pivot,i),
        tis.merge(pivot,i);
    int K=0;
    for(auto[X,Y]:tre)
        if(tis.merge(X,Y))
            AD(X,Y),K-=col[parind[Y]];
    return K+Q();
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    for(int i=0;i<n;i++)
        col[i]=1;
    U=u;
    V=v;
    N_=n;
    int m=u.size();
    for(int i=0;i<m;i++)
        AADJ[u[i]].push_back(v[i]),
        AADJ[v[i]].push_back(u[i]),
        indexofr[u[i]][v[i]]=indexofr[v[i]][u[i]]=i+1;
    gendfstree(0,0);
    for(auto[X,Y]:tre)
        AD(X,Y);
    for(int i=0;i<n;i++){
        vector<int>v;
        for(int j=0;j<n;j++)
            if(indexofr[i][j])
                v.push_back(j);
        deg[i]=countst(v,i);
    }
    set<int>st;
    for(int i=0;i<n;i++)
        st.insert(i);
    vector<int>done;
    for(int i=1;i<n;i++){
        int x=0;
        for(int i=0;i<n;i++)
            if(deg[i]==1)x=i;
        R.clear();
        deg[x]=0;
        st.erase(x);
        vector<int>V;
        for(auto i:st)
            if(indexofr[i][x])
                V.push_back(i);
        while(V.size()>1){
            vector<int>a[2];
            for(int i=0;i<V.size();i++)
                a[i%2].push_back(V[i]);
            V=a[countst(a[1],x)];
        }
        deg[V[0]]--;
        ans.push_back(indexofr[x][V[0]]-1);
    }
    R=ans;
    //assert(Q()==n-1);
    return ans;
}

Compilation message (stderr)

simurgh.cpp: In member function 'bool dsu::merge(int, int)':
simurgh.cpp:37:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |         return par[a]=b;
      |                ~~~~~~^~
simurgh.cpp: In function 'void calcfortree(int)':
simurgh.cpp:60:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         while(path2.size()>d+1) {
      |               ~~~~~~~~~~~~^~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:158:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |             for(int i=0;i<V.size();i++)
      |                         ~^~~~~~~~~

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