제출 #594456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
594456		andrei_boaca	Potemkin cycle (CEOI15_indcyc)	C++14	60 / 100	75 ms	6232 KiB

indcyc

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,m;
vector<pii> edges;
vector<int> muchii[1005];
bool adj[1005][1005];
int dp[1005][22],par[1005],dist[1005][1005],niv[1005],in[1005],out[1005],from[1005];
int comp[1005];
bool use[1005];
int Dp[1005];
int timp;
bool isancestor(int a,int b)
{
    return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b)
{
    if(niv[a]>niv[b])
        swap(a,b);
    if(isancestor(a,b))
        return a;
    for(int i=12;i>=0;i--)
        if(dp[a][i]!=0&&!isancestor(dp[a][i],b))
            a=dp[a][i];
    return par[a];
}
void Dfs(int nod)
{
    timp++;
    in[nod]=timp;
    use[nod]=1;
    dp[nod][0]=par[nod];
    for(int i=1;i<=12;i++)
        dp[nod][i]=dp[dp[nod][i-1]][i-1];
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            niv[i]=niv[nod]+1;
            Dfs(i);
        }
    out[nod]=timp;
}
bool cmp(pii a, pii b)
{
    int d1=dist[a.first][a.second];
    int d2=dist[b.first][b.second];
    return d1<d2;
}
bool block[1005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        comp[i]=i;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(comp[a]!=comp[b])
        {
            muchii[a].push_back(b);
            muchii[b].push_back(a);
            int c2=comp[b];
            for(int j=1;j<=n;j++)
                if(comp[j]==c2)
                    comp[j]=comp[a];
        }
        else
            edges.push_back({a,b});
    }
    for(int i=1;i<=n;i++)
        if(!use[i])
        {
            timp=0;
            niv[i]=1;
            Dfs(i);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(comp[i]==comp[j])
            {
                int lca=LCA(i,j);
                dist[i][j]=niv[i]-niv[lca]+niv[j]-niv[lca]+1;
            }
    sort(edges.begin(),edges.end(),cmp);
    for(auto i:edges)
    {
        int a=i.first;
        int b=i.second;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
        int lca=LCA(a,b);
        vector<int> v1,v2;
        while(a!=lca)
        {
            v1.push_back(a);
            a=par[a];
        }
        while(b!=lca)
        {
            v2.push_back(b);
            b=par[b];
        }
        vector<int> v;
        for(auto j:v1)
            v.push_back(j);
        v.push_back(lca);
        reverse(v2.begin(),v2.end());
        for(auto j:v2)
            v.push_back(j);
        if(v.size()>=4)
        {
            for(int i:v)
                block[i]=0;
            int unblocked=v.size();
            unblocked-=2;
            while(unblocked>1)
            {
                vector<int> vals;
                for(int j=0;j<v.size();j++)
                {
                    if(j==0)
                        Dp[v[j]]=1;
                    else
                        Dp[v[j]]=1e9;
                    int x=v[j];
                    if(block[x])
                        continue;
                    from[x]=0;
                    for(int k=j-1;k>=0;k--)
                    {
                        int y=v[k];
                        if(block[y])
                            continue;
                        if(adj[x][y]||k==j-1)
                        {
                            Dp[x]=min(Dp[x],Dp[y]+1);
                            if(Dp[y]+1==Dp[x])
                                from[x]=y;
                        }
                    }
                }
                int last=v.back();
                if(Dp[last]==1e9)
                    break;
                if(Dp[last]>=4)
                {
                    vector<int> vals;
                    while(true)
                    {
                        vals.push_back(last);
                        if(last==v[0])
                            break;
                        last=from[last];
                    }
                    for(int j:vals)
                        cout<<j<<' ';
                    return 0;
                }
                block[from[last]]=1;
                unblocked--;
            }
        }
        adj[i.first][i.second]=adj[i.second][i.first]=1;
    }
    cout<<"no";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

indcyc.cpp: In function 'int main()':
indcyc.cpp:125:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |                 for(int j=0;j<v.size();j++)
      |                             ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10