oj.uz

Submission #113042

# Submission time Handle Problem Language Result Execution time Memory
113042 2019-05-23T10:07:57 Z Mahdi_Jfri Potemkin cycle (CEOI15_indcyc) C++14
0 / 100
 25 ms 1920 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define hash Hash

const int maxn = 1e3 + 20;
const int base = 4001;
const int mod = 1e9 + 7;

bool visited[maxn] , A[maxn][maxn];

int pw[maxn] , d[maxn] , deg[maxn] , hash[maxn] , p[maxn];

vector<int> adj[maxn];

inline void mkay(int &a)
{
	if(a >= mod)
		a -= mod;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	pw[0] = 1;
	for(int i = 1; i < maxn; i++)
		pw[i] = 1LL * pw[i - 1] * base % mod;

	int n , m;
	cin >> n >> m;

	for(int i = 0; i < m; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;

		adj[a].pb(b);
		adj[b].pb(a);

		A[a][b] = A[b][a] = 1;
	}

	for(int src = 0; src < n; src++)
	{
		queue<int> q;

		memset(visited , 0 , sizeof visited);
		memset(d , 63 , sizeof d);

		q.push(src);
		d[src] = 0;
		visited[src] = 1;

		while(!q.empty())
		{
			int v = q.front();
			q.pop();

			for(auto u : adj[v])
				if(!visited[u])
					visited[u] = 1 , d[u] = d[v] + 1 , p[u] = v , q.push(u);
		}

		for(int v = 0; v < n; v++)
			if(d[v] == 3)
				return cout << v + 1 << " " << p[v] + 1 << " " << p[p[v]] + 1 << " " << src + 1 << endl , 0;
		
		for(int v = 0; v < n; v++)
			if(visited[v] && d[v] == 2)
			{
				deg[v] = hash[v] = 0;
				for(auto u : adj[v])
					if(d[u] == 1)
						deg[v]++ , mkay(hash[v] += pw[u]);
			}

		for(int v = 0; v < n; v++)
			if(visited[v] && d[v] == 2)
				for(auto u : adj[v])
					if(d[u] == 2 && (deg[v] != deg[u] || hash[v] != hash[u]))
						for(int w = 0; w < n; w++)
							if(A[src][w] && A[w][v] && !A[w][u])
								return cout << src + 1 << " " << w + 1 << " " << v + 1 << " " << u + 1 << endl , 0;
	}

	cout << "no" << endl;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 768 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 3 ms 768 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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