제출 #1156141

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

simurgh

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

using namespace std;

const int nx=505;

int vs[nx], edg[nx][nx], deg[nx], vl[nx][nx], mx, used[nx];
vector<int> qrs, tmp, res;

std::vector<int> find_roads(int n, std::vector<int> _u, std::vector<int> _v) {
	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;
    for (int i=1; i<n; i++)
    {
        qrs.clear();
        for (int j=0; j<n; j++) if (j!=i) qrs.push_back(edg[i][j]);
        deg[i]=count_common_roads(qrs);
    }
    qrs.clear();
    for (int i=1; i<n-1; i++) qrs.push_back(edg[i][i+1]);
    tmp.resize(n);
    for (int i=1; i<n; i++)
    {
        qrs.push_back(edg[0][i]);
        tmp[i]=count_common_roads(qrs);
        qrs.pop_back();
        mx=max(mx, tmp[i]);
    }
    for (int i=1; i<n; i++)
    {
        if (tmp[i]==mx) deg[i]--, vl[0][i]=vl[i][0]=1;
        else vl[0][i]=vl[i][0]=0;
    }
    for (int i=1; i<n; i++)
    {
        //cout<<"deg "<<i<<' '<<deg[i]<<'\n';
        while (deg[i]>0)
        {
            vector<int> bs;
            for (int j=0; j<n; j++) if (j!=i&&vl[i][j]==-1) bs.push_back(j);
            int l=0, r=bs.size()-1;
            while (l<r)
            {
                int md=(l+r)/2, expected=0;
                for (int j=0; j<n; j++) used[j]=0;
                qrs.clear();
                for (int j=l; j<=md; j++) qrs.push_back(edg[i][bs[j]]), used[i]=used[bs[j]]=1;
                if (!used[0]) used[0]=1, expected+=vl[i][0], qrs.push_back(edg[i][0]);
                for (int j=0; j<n; j++) if (!used[j]) qrs.push_back(edg[0][j]), expected+=vl[0][j];
                if (count_common_roads(qrs)==expected) 
                {
                    for (int j=l; j<=md; j++) vl[i][bs[j]]=vl[bs[j]][i]=0;
                    l=md+1;
                }
                else r=md;
            }
            vl[i][bs[l]]=vl[bs[l]][i]=1;
            //cout<<"edge "<<i<<' '<<bs[l]<<'\n';
            deg[i]--;
            deg[bs[l]]--;
        }
    }
    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]);
    return res;
}

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