Submission #594440

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
594440	2022-07-12T12:56:53 Z	andrei_boaca	Potemkin cycle (CEOI15_indcyc)	C++14	60 / 100	56 ms	6200 KB

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;
}
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;
        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);
        bool ok=1;
        /*for(int x:v)
            for(int y:v)
                if(adj[x][y])
                    ok=0;*/
        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];
            from[x]=0;
            for(int k=j-1;k>=0;k--)
            {
                int y=v[k];
                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]>=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;
        }
        adj[i.first][i.second]=adj[i.second][i.first]=1;
    }
    cout<<"no";
    return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int j=0;j<v.size();j++)
      |                     ~^~~~~~~~~
indcyc.cpp:113:14: warning: unused variable 'ok' [-Wunused-variable]
  113 |         bool ok=1;
      |              ^~

Subtask #1
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct
5	Correct	340 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	724 KB	Output is correct

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	852 KB	Expected integer, but "no" found
2	Halted	0 ms	0 KB	-

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1876 KB	Output is correct
2	Correct	8 ms	1876 KB	Output is correct
3	Correct	6 ms	1996 KB	Output is correct
4	Correct	10 ms	1892 KB	Output is correct

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	1876 KB	Expected integer, but "no" found
2	Halted	0 ms	0 KB	-

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	5928 KB	Output is correct
2	Correct	44 ms	5672 KB	Output is correct
3	Correct	56 ms	6200 KB	Output is correct
4	Correct	44 ms	5752 KB	Output is correct

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	37 ms	5624 KB	Expected integer, but "no" found
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	55 ms	3396 KB	Expected integer, but "no" found
2	Halted	0 ms	0 KB	-