Submission #892303

#	Time	Username	Problem	Language	Result	Execution time	Memory
892303		abcvuitunggio	Simurgh (IOI17_simurgh)	C++17	51 / 100	513 ms	8672 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
    int u,v;
}e[150000];
int n,m,ch[150000],p[150000],used[150000],tin[501],tout[501],t,par[501],cur;
vector <int> ke[150000],ve;
set <int> s;
int ask(set <int> s){
    vector <int> r;
    for (int i:s)
        r.push_back(i);
    return count_common_roads(r);
}
int f(int i){
    return (p[i]==i?i:p[i]=f(p[i]));
}
bool unite(int i, int j){
    i=f(i);
    j=f(j);
    if (i==j)
        return false;
    p[j]=i;
    return true;
}
bool create_random_spanning_tree(){
    iota(p,p+n+1,0);
    for (int i=0;i<n;i++)
        ke[i].clear();
    s.clear();
    for (int i=0;i<m;i++)
        if (ch[i]==1){
            used[i]=unite(e[i].u,e[i].v);
            if (used[i]){
                ke[e[i].u].push_back(i);
                ke[e[i].v].push_back(i);
                s.insert(i);
            }
        }
    if (s.size()==n-1)
        return false;
    for (int i=0;i<m;i++)
        if (ch[i]==-1){
            used[i]=unite(e[i].u,e[i].v);
            if (used[i]){
                ke[e[i].u].push_back(i);
                ke[e[i].v].push_back(i);
                s.insert(i);
            }
        }
    cur=ask(s);
    return true;
}
void dfs(int u, int parent){
    tin[u]=++t;
    for (int i:ke[u]){
        int v=e[i].u^e[i].v^u;
        if (v!=parent){
            par[v]=i;
            dfs(v,u);
        }
    }
    tout[u]=t;
}
bool isancestor(int u, int v){
    return (tin[u]<=tin[v]&&tout[u]>=tout[v]);
}
void get_path(int u, int v){
    ve.clear();
    while (!isancestor(u,v)){
        ve.push_back(par[u]);
        u^=e[par[u]].u^e[par[u]].v;
    }
    while (!isancestor(v,u)){
        ve.push_back(par[v]);
        v^=e[par[v]].u^e[par[v]].v;
    }
}
vector <int> find_roads(int N, vector <int> u, vector <int> v){
    n=N,m=u.size();
    for (int i=0;i<m;i++)
        e[i]={u[i],v[i]};
    fill(ch,ch+m,-1);
    while (create_random_spanning_tree()){
        t=0;
        dfs(0,0);
        int restart=0;
        for (int i=0;i<m;i++)
            if (!used[i]&&ch[i]==-1){
                get_path(u[i],v[i]);
                for (int j:ve){
                    if (ch[j]==1){
                        s.erase(j);
                        s.insert(i);
                        ch[i]=1-cur+ask(s);
                        s.erase(i);
                        s.insert(j);
                        break;
                    }
                }
                if (ch[i]==0)
                    continue;
                if (ch[i]==1){
                    restart=1;
                    break;
                }
                int mx=-1;
                for (int j:ve){
                    s.erase(j);
                    s.insert(i);
                    ch[j]=ask(s)-cur;
                    mx=max(mx,ch[j]);
                    s.erase(i);
                    s.insert(j);
                }
                if (mx==1){
                    ch[i]=1;
                    restart=1;
                    for (int j:ve)
                        ch[j]^=1;
                    break;
                }
                ch[i]=0;
                for (int j:ve)
                    ch[j]=-ch[j];
                restart=1;
                break;
            }
        if (!restart)
            break;
    }
    vector <int> res;
    for (int i:s)
        res.push_back(i);
    return res;
}

Compilation message (stderr)

simurgh.cpp: In function 'bool create_random_spanning_tree()':
simurgh.cpp:41:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     if (s.size()==n-1)
      |         ~~~~~~~~^~~~~

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