oj.uz

Submission #208326

# Submission time Handle Problem Language Result Execution time Memory
208326 2020-03-10T18:56:47 Z stefdasca Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 308 ms 98168 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

int n, m;
int mat[2002][2002];

int tt[2002], st, dr;
int viz[200002];

pair<int, int> muchii[200002];

vector<pair<int, int> > v[2002];
vector<int> v2[200002], v3[2002];

void dfs(int dad, int nod)
{
	viz[nod] = 1;
    for(int i = 0; i < v2[nod].size(); ++i)
	{
	    int vecin = v2[nod][i];
		if(!st && viz[vecin] == 1)
		{
			st = vecin, dr = nod;
			break;
		}
		if(!viz[vecin])
		{
			tt[vecin] = nod;
			dfs(nod, vecin);
		}
	}
	viz[nod] = 2;
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

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

		mat[a][b] = mat[b][a] = 1;
		muchii[i] = {a, b};

		v[a].pb({b, i});
		v[b].pb({a, i+m});
	}

	for (int i = 1; i <= m; i++)
	{
		int a = muchii[i].fi;
		int b = muchii[i].se;
		for(int j = 0; j < v[b].size(); ++j)
		{
			int w = v[b][j].fi;
			int e = v[b][j].se;
			if (w != a && w != b && !mat[w][a])
				v2[i].pb(e);
		}
		for(int j = 0; j < v[a].size(); ++j)
		{
			int w = v[a][j].fi;
			int e = v[a][j].se;
			if (w != a && w != b && !mat[w][b])
				v2[i+m].pb(e);
		}
	}
	for(int i = 1; !st && i <= 2*m; i++)
		if(!viz[i])
			dfs(0, i);
	if(!st)
	{
		printf("no\n");
		return 0;
	}
	int nr = dr;
	vector<int> sol;
	while(1)
	{
		if(nr > m)
			sol.pb(muchii[nr-m].se);
		else
			sol.pb(muchii[nr].fi);
		if(nr == st)
            break;
		nr = tt[nr];
	}
	for(int i = 0; i < sol.size(); ++i)
        cout << sol[i] << " ";
	cout << '\n';
	return 0;
}

Compilation message

indcyc.cpp: In function 'void dfs(int, int)':
indcyc.cpp:21:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v2[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < v[b].size(); ++j)
                  ~~^~~~~~~~~~~~~
indcyc.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < v[a].size(); ++j)
                  ~~^~~~~~~~~~~~~
indcyc.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < sol.size(); ++i)
                 ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5240 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7032 KB Output is correct
2 Correct 11 ms 7160 KB Output is correct
3 Correct 17 ms 9080 KB Output is correct
4 Correct 18 ms 9080 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 29944 KB Output is correct
2 Correct 39 ms 16760 KB Output is correct
3 Correct 122 ms 29944 KB Output is correct
4 Correct 39 ms 16760 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 57988 KB Output is correct
2 Correct 174 ms 62072 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 11512 KB Output is correct
2 Correct 237 ms 11772 KB Output is correct
3 Correct 307 ms 98168 KB Output is correct
4 Correct 308 ms 98140 KB Output is correct