제출 #893928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
893928		abcvuitunggio	Simurgh (IOI17_simurgh)	C++17	100 / 100	855 ms	16920 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
    int u,v;
}e[150000];
int n,m,ch[150000],low[501],tin[501],tout[501],t,par[501],cur,p[501];
vector <int> ve,res;
set <int> s,ke[501];
int ask(set <int> s){
    vector <int> r;
    for (int i:s)
        r.push_back(i);
    return count_common_roads(r);
}
void dfs(int u, int parent){
    tin[u]=low[u]=++t;
    for (int i:ke[u]){
        int v=e[i].u^e[i].v^u;
        if (v!=parent){
            if (!tin[v]){
                s.insert(i);
                par[v]=i;
                dfs(v,u);
                low[u]=min(low[u],low[v]);
                if (low[v]==tin[v])
                    ch[i]=1;
            }
            else
                low[u]=min(low[u],tin[v]);
        }
    }
    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;
    }
}
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;
}
int calc(set <int> s2){
    iota(p,p+n,0);
    for (int i:s2)
        unite(e[i].u,e[i].v);
    int cnt=0;
    for (int i:s)
        if (unite(e[i].u,e[i].v)){
            s2.insert(i);
            cnt+=ch[i];
        }
    return ask(s2)-cnt;
}
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]};
        ke[u[i]].insert(i);
        ke[v[i]].insert(i);
    }
    fill(ch,ch+m,-1);
    dfs(0,0);
    cur=ask(s);
    for (int i=0;i<m;i++)
        if (s.find(i)==s.end()){
            get_path(u[i],v[i]);
            int c=1;
            for (int j:ve)
                if (ch[j]==-1)
                    c=0;
            if (c)
                continue;
            for (int j:ve){
                if (ch[j]!=-1){
                    s.erase(j);
                    s.insert(i);
                    ch[i]=(ch[j]?1-cur+ask(s):ask(s)-cur);
                    s.erase(i);
                    s.insert(j);
                    break;
                }
            }
            if (ch[i]!=-1){
                for (int j:ve)
                    if (ch[j]==-1){
                        s.erase(j);
                        s.insert(i);
                        ch[j]=(ch[i]?1+cur-ask(s):cur-ask(s));
                        s.erase(i);
                        s.insert(j);
                    }
                continue;
            }
            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;
                for (int j:ve)
                    ch[j]^=1;
                continue;
            }
            ch[i]=0;
            for (int j:ve)
                ch[j]=-ch[j];
        }
    vector <int> tmp;
    set <int> S;
    for (int i=0;i<n;i++){
        int deg=calc(ke[i]);
        while (deg){
            tmp.clear();
            for (int j:ke[i])
                tmp.push_back(j);
            int l=0,r=tmp.size()-1,kq=-1;
            while (l<=r){
                int mid=(l+r)>>1;
                S.clear();
                for (int i=0;i<=mid;i++)
                    S.insert(tmp[i]);
                if (calc(S)==deg){
                    kq=tmp[mid];
                    r=mid-1;
                }
                else
                    l=mid+1;
            }
            res.push_back(kq);
            ke[u[kq]].erase(kq);
            ke[v[kq]].erase(kq);
            deg--;
        }
    }
    return res;
}

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