제출 #1156249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156249		12345678	Simurgh (IOI17_simurgh)	C++20	100 / 100	266 ms	4464 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=505;

int N, edg[nx][nx], vl[nx][nx], dsu[nx], vs[nx], f[nx], cnt, sv[nx], def[nx], mx, resq[nx];
vector<int> g[nx], nd[nx], qrs, tem, bs, res;
vector<tuple<int, int, int>> t;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

void dfs(int u, int st, int cur)
{
    for (int v=0; v<N; v++)
    {
        if (vs[v]||edg[u][v]==-1) continue;
        if (v==st)
        {
            def[cur]=u;
            if (vl[u][v]>=0) sv[cur]=u;
            else if (!f[u]) nd[cur].push_back(u);
        }
        else vs[v]=1, tem.push_back(edg[u][v]), dfs(v, st, cur);
    }
}

int check(int l, int r, int st)
{
    //cout<<"here "<<st<<' '<<l<<' '<<r<<'\n';
    qrs.clear();
    int expected=0;
    for (int i=l; i<=r; i++) dsu[find(bs[i])]=find(st), qrs.push_back(edg[st][bs[i]]);
    //cout<<"before ";
    //for (auto x:qrs) cout<<x<<' ';
    //cout<<'\n';
    for (auto [u, v, w]:t) if (find(u)!=find(v)) expected+=w, dsu[find(u)]=find(v), qrs.push_back(edg[u][v]);
    if (count_common_roads(qrs)>expected) return 1;
    return 0;
}

std::vector<int> find_roads(int n, std::vector<int> _u, std::vector<int> _v) {
    N=n;
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) edg[i][j]=-1;
    for (int i=0; i<_u.size(); i++) edg[_u[i]][_v[i]]=edg[_v[i]][_u[i]]=i;
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) vl[i][j]=-1;
    queue<int> q;
    q.push(0);
    f[0]=1;
    while (!q.empty())
    {
        auto u=q.front();
        q.pop();
        cnt=0;
        for (int i=0; i<n; i++) vs[i]=0;
        tem.clear();
        for (int v=0; v<n; v++)
        {
            if (edg[u][v]==-1||vs[v]) continue;
            sv[cnt]=-1;
            vs[v]=1;
            dfs(v, u, cnt);
            cnt++;
        }
        //cout<<"debug "<<u<<' '<<cnt<<'\n';
        for (int i=0; i<cnt; i++)
        {
            if (nd[i].empty()) continue;
            //cout<<"here "<<i<<' '<<sv[i]<<' '<<def[i]<<'\n';
            qrs=tem;
            for (int j=0; j<cnt; j++) if (i!=j) qrs.push_back(edg[u][def[j]]);
            if (sv[i]==-1)
            {
                mx=0;
                int sz=nd[i].size();
                for (int j=0; j<sz; j++)
                {
                    qrs.push_back(edg[u][nd[i][j]]);
                    resq[j]=count_common_roads(qrs);
                    qrs.pop_back();
                    mx=max(mx, resq[j]);
                }
                for (int j=0; j<sz; j++)
                {
                    int v=nd[i][j];
                    f[v]=1;
                    q.push(v);
                    vl[u][v]=vl[v][u]=(resq[j]==mx);
                    t.push_back({u, v, vl[u][v]});
                }
            }
            else
            {
                qrs.push_back(edg[u][sv[i]]);
                int ref=count_common_roads(qrs);
                qrs.pop_back();
                int sz=nd[i].size();
                for (int j=0; j<sz; j++)
                {
                    int v=nd[i][j];
                    qrs.push_back(edg[u][v]);
                    int ans=count_common_roads(qrs);
                    qrs.pop_back();
                    f[v]=1;
                    q.push(v);
                    if (ans<ref) vl[u][v]=vl[v][u]=0;
                    if (ans==ref) vl[u][v]=vl[v][u]=vl[u][sv[i]];
                    if (ans>ref) vl[u][v]=vl[v][u]=1;
                    t.push_back({u, v, vl[u][v]});
                }
            }
        }
        for (int i=0; i<cnt; i++) g[i].clear(), nd[i].clear();
    }
    //for (auto [u, v, w]:t) cout<<"t "<<u<<' '<<v<<' '<<w<<'\n';
    for (int u=0; u<n; u++)
    {
        while (1)
        {
            bs.clear();
            for (int v=0; v<n; v++) if (edg[u][v]!=-1&&vl[u][v]==-1) bs.push_back(v);
            int l=0, r=bs.size()-1;
            if (bs.empty()) break;
            for (int i=0; i<n; i++) dsu[i]=i;
            if (check(l, r, u))
            {
                while (l<r)
                {
                    int md=(l+r)/2;
                    for (int i=0; i<n; i++) dsu[i]=i;
                    if (check(l, md, u)) r=md;
                    else
                    {
                        for (int i=l; i<=md; i++) vl[u][bs[i]]=vl[bs[i]][u]=0;
                        l=md+1;
                    }
                }
                vl[u][bs[l]]=vl[bs[l]][u]=1;
            }
            else
            {
                for (auto x:bs) vl[u][x]=vl[x][u]=0;
                break;
            }
        }
    }
    for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) if (vl[i][j]==1) res.push_back(edg[i][j]);
    //for (auto x:res) cout<<x<<' ';
    //cout<<'\n';
    return res;
}

/*
4 4
0 1
1 2
1 3
2 3
0 1 2
*/

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