oj.uz

Submission #287808

# Submission time Handle Problem Language Result Execution time Memory
287808 2020-09-01T02:10:55 Z wjdqhdhfflavldkem12 None (KOI17_cat) C++14
0 / 100
 299 ms 23292 KB 
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

typedef int node;

typedef struct {
	node nd;
	int num;
}edge;


int n, m, ans;
bool visited[300010];
bool edgeuse[300010];
int in_cycle[300010];
vector<edge> adjList[300010];
vector<node> cycle[2];
vector<node> ctemp;
int cnum = 0, csize = 0;

void dfs(int current);

int main(){
	int i, j;

	scanf("%d %d", &n, &m);

	node a, b, nume = 1;
	for (i = 0; i < m; i++){
		scanf("%d %d", &a, &b);
		adjList[a].push_back({ b, nume });
		adjList[b].push_back({ a, nume });
		nume++;
	}

	dfs(1);

	if (cnum == 1){
		for (i = 0; i < cycle[0].size(); i++){
			ans += cycle[0][i];
		}
	}
	else{
		vector<int> same, order;
		int k = 0;
		for (i = 0; i < cycle[0].size(); i++)
			in_cycle[cycle[0][i]] = i + 1;
		for (j = 0; k < cycle[1].size(); j++, k++){
			if (in_cycle[cycle[1][j]]){
				i = in_cycle[cycle[1][j]] - 1;
				while (cycle[0][i] == cycle[1][j]){
					same.push_back(cycle[1][j]);
					order.push_back(k);
					i++; j++; k++;
					if (i == cycle[0].size())
						i = 0;
					if (j == cycle[1].size())
						j = 0;
				}
				j--; k--;
			}
		}

		for (i = 1; i < same.size() - 1; i++){
			if (order[i - 1] + 1 == order[i] && order[i] + 1 == order[i + 1])
				same[i] = 0;
		}

		for (i = 0; i < same.size();i++){
			if (same[i] == 0)
				continue;
			cnum = 0; csize = 0; cycle[0].clear(); cycle[1].clear(); ctemp.clear();
			for (j = 0; j < 300010; j++){
				visited[j] = false;
				edgeuse[j] = false;
			}
			visited[same[i]] = true;
			for (j = 0; j < adjList[same[i]].size(); j++)
				edgeuse[adjList[same[i]][j].num] = true;

			if (same[i] == 1)
				dfs(2);
			else
				dfs(1);

			
			if (cnum == 0)
				ans += same[i];
		}
	}

	printf("%d\n", ans);


	return 0;
}

void dfs(int curr){
	int i, j, ans;
	edge next;
	vector<edge> stack;

	stack.push_back({ curr, 0 });
	
	while (1){
		if (cnum == 2)
			break;
		if (stack.empty())
			break;
		edge current;

		current = stack.back();
		stack.pop_back();

		if (visited[current.nd]){
			if (ctemp.back() == current.nd){
				ctemp.pop_back();
				csize--;
			}
			continue;
		}
		
		visited[current.nd] = true;
		edgeuse[current.num] = true;
		ctemp.push_back(current.nd);
		csize++;

		for (i = 0; i < adjList[current.nd].size(); i++){
			if (cnum == 2)
				break;
			next = adjList[current.nd][i];
			if (!visited[next.nd]){
				if (!edgeuse[next.num])
					stack.push_back({ next.nd, next.num });
			}
			else if (!edgeuse[next.num]){
				edgeuse[next.num] = true;
				for (j = 0; j < csize; j++){
					if (ctemp[j] == next.nd)
						break;
				}
				cycle[cnum].assign(ctemp.begin() + j, ctemp.end());
				cnum++;
			}
		}

	}

	return;
}

Compilation message

cat.cpp: In function 'int main()':
cat.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (i = 0; i < cycle[0].size(); i++){
      |               ~~^~~~~~~~~~~~~~~~~
cat.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (i = 0; i < cycle[0].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~~
cat.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (j = 0; k < cycle[1].size(); j++, k++){
      |               ~~^~~~~~~~~~~~~~~~~
cat.cpp:58:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |      if (i == cycle[0].size())
      |          ~~^~~~~~~~~~~~~~~~~~
cat.cpp:60:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |      if (j == cycle[1].size())
      |          ~~^~~~~~~~~~~~~~~~~~
cat.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (i = 1; i < same.size() - 1; i++){
      |               ~~^~~~~~~~~~~~~~~~~
cat.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (i = 0; i < same.size();i++){
      |               ~~^~~~~~~~~~~~~
cat.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    for (j = 0; j < adjList[same[i]].size(); j++)
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~
cat.cpp: In function 'void dfs(int)':
cat.cpp:131:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for (i = 0; i < adjList[current.nd].size(); i++){
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cat.cpp:102:12: warning: unused variable 'ans' [-Wunused-variable]
  102 |  int i, j, ans;
      |            ^~~
cat.cpp: In function 'int main()':
cat.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
cat.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7936 KB Output is correct
2 Correct 6 ms 7936 KB Output is correct
3 Correct 7 ms 8064 KB Output is correct
4 Correct 6 ms 7936 KB Output is correct
5 Incorrect 8 ms 7680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 299 ms 22688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 23292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7936 KB Output is correct
2 Correct 6 ms 7936 KB Output is correct
3 Correct 7 ms 8064 KB Output is correct
4 Correct 6 ms 7936 KB Output is correct
5 Incorrect 8 ms 7680 KB Output isn't correct
6 Halted 0 ms 0 KB -