oj.uz

Submission #287810

# Submission time Handle Problem Language Result Execution time Memory
287810 2020-09-01T02:28:01 Z wjdqhdhfflavldkem12 None (KOI17_cat) C++14
0 / 100
 275 ms 22180 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);
 
  	if (n == 2){
		printf("3\n");
		return 0;
	}
  
	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:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (i = 0; i < cycle[0].size(); i++){
      |               ~~^~~~~~~~~~~~~~~~~
cat.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (i = 0; i < cycle[0].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~~
cat.cpp:56:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (j = 0; k < cycle[1].size(); j++, k++){
      |               ~~^~~~~~~~~~~~~~~~~
cat.cpp:63:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |      if (i == cycle[0].size())
      |          ~~^~~~~~~~~~~~~~~~~~
cat.cpp:65:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |      if (j == cycle[1].size())
      |          ~~^~~~~~~~~~~~~~~~~~
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 = 1; i < same.size() - 1; i++){
      |               ~~^~~~~~~~~~~~~~~~~
cat.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (i = 0; i < same.size();i++){
      |               ~~^~~~~~~~~~~~~
cat.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    for (j = 0; j < adjList[same[i]].size(); j++)
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~
cat.cpp: In function 'void dfs(int)':
cat.cpp:136:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |   for (i = 0; i < adjList[current.nd].size(); i++){
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cat.cpp:107:12: warning: unused variable 'ans' [-Wunused-variable]
  107 |  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:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |   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 7 ms 7936 KB Output is correct
5 Incorrect 7 ms 7552 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 22180 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 7 ms 7936 KB Output is correct
5 Incorrect 7 ms 7552 KB Output isn't correct
6 Halted 0 ms 0 KB -