Submission #40449

#	Time	Username	Problem	Language	Result	Execution time	Memory
40449		Pajaraja	Potemkin cycle (CEOI15_indcyc)	C++14	100 / 100	300 ms	5116 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;
vector<int> g[1007],d,k;
bool m[1007][1007],vi[1007],uc[1007];
int p[1007];
void dfs(int s,int og)
{
	vi[s]=true;
	if(m[s][og]) 
	{
	    k.push_back(s);
	    d.push_back(s);
	    return;
	}
	for(int i=0;i<g[s].size();i++) if(!vi[g[s][i]]) dfs(g[s][i],og);
}
void bfs(int s,int l,int r)
{
	fill(p,p+1007,-1);
	queue<int> q;
	p[s]=0;
	p[l]=s;
	q.push(l);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<g[u].size();i++) if(p[g[u][i]]==-1 && !m[g[u][i]][s])
		{
			p[g[u][i]]=u;
			q.push(g[u][i]);
		}
	}
	int x=r;
	while(x>0)
	{
		printf("%d ",x);
		x=p[x];
	}
}
int main()
{
	int n,ma;
	scanf("%d%d",&n,&ma);
	for(int i=0;i<ma;i++)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		g[t1].push_back(t2);
		g[t2].push_back(t1);
		m[t1][t2]=m[t2][t1]=true;
	}
	for(int i=1;i<=n;i++) m[i][i]=true;
	for(int i=1;i<=n;i++)
	{
		int cnt=0;
		fill(vi,vi+1+n,false);
		for(int j=1;j<=n;j++) if(!vi[j] && !m[i][j] && i!=j)
		{
			k.clear();
		    dfs(j,i);
		    for(int z=0;z<d.size();z++) vi[z]=false;
		    d.clear();
		    cnt++;
		    for(int z=0;z<k.size();z++) for(int t=z+1;t<k.size();t++) if(!m[k[z]][k[t]])
		    {
		    	bfs(i,k[z],k[t]);
		    	return 0;
			}
		}
	}
	printf("no");
}

Compilation message (stderr)

indcyc.cpp: In function 'void dfs(int, int)':
indcyc.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(!vi[g[s][i]]) dfs(g[s][i],og);
               ^
indcyc.cpp: In function 'void bfs(int, int, int)':
indcyc.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[u].size();i++) if(p[g[u][i]]==-1 && !m[g[u][i]][s])
                ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int z=0;z<d.size();z++) vi[z]=false;
                    ^
indcyc.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int z=0;z<k.size();z++) for(int t=z+1;t<k.size();t++) if(!m[k[z]][k[t]])
                    ^
indcyc.cpp:65:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int z=0;z<k.size();z++) for(int t=z+1;t<k.size();t++) if(!m[k[z]][k[t]])
                                                  ^
indcyc.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&ma);
                      ^
indcyc.cpp:48:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t1,&t2);
                        ^

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