oj.uz

Submission #40446

# Submission time Handle Problem Language Result Execution time Memory
40446 2018-02-01T14:11:52 Z Pajaraja Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 213 ms 3268 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)
{
	if(m[s][og]) 
	{
	    k.push_back(s);
	    vi[s]=true;
	    d.push_back(s);
	    return;
	}
	vi[s]=true;
	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)
		{
			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;
		    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:16: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:29: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)
                ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:63: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:45: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:49: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 Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 2 ms 528 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 532 KB Wrong adjacency

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 536 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 708 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 1196 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 1196 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 2696 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 2872 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3268 KB Wrong adjacency
2 Halted 0 ms 0 KB -