oj.uz

Submission #40449

# Submission time Handle Problem Language Result Execution time Memory
40449 2018-02-01T14:43:39 Z Pajaraja Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 300 ms 5116 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Too short sequence
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 1 ms 496 KB Output is correct
5 Correct 1 ms 496 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Too short sequence

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 532 KB Too short sequence
2 Correct 2 ms 536 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 536 KB Too short sequence

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 660 KB Too short sequence
2 Correct 2 ms 660 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 924 KB Output is correct
2 Correct 3 ms 924 KB Too short sequence
3 Correct 4 ms 924 KB Too short sequence
4 Correct 11 ms 1240 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1240 KB Too short sequence
2 Correct 8 ms 1240 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2324 KB Too short sequence
2 Correct 14 ms 2324 KB Too short sequence
3 Correct 300 ms 2888 KB Output is correct
4 Correct 159 ms 2888 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2888 KB Too short sequence
2 Correct 120 ms 2992 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3016 KB Too short sequence
2 Correct 25 ms 3656 KB Output is correct
3 Correct 28 ms 4588 KB Too short sequence
4 Correct 285 ms 5116 KB Output is correct