oj.uz

Submission #30113

# Submission time Handle Problem Language Result Execution time Memory
30113 2017-07-22T06:32:08 Z khsoo01 Garbage (POI11_smi) C++11
100 / 100
 1269 ms 137024 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 100005, M = 1000005;

int n, m, cur[N];
bool vis[M], ins[N];

vector<pii> adj[N];
vector<int> st;
vector<vector<int> > ans;

void dfs (int C) {
	if(ins[C]) {
		vector<int> T;
		T.push_back(C);
		while(true) {
			int X = st.back();
			st.pop_back();
			ins[X] = false;
			T.push_back(X);
			if(X == C) break;
		}
		ans.push_back(T);
	}
	while(cur[C] < adj[C].size()) {
		auto T = adj[C][cur[C]++];
		int A, B; tie(A, B) = T;
		if(vis[B]) continue;
		vis[B] = true; ins[C] = true;
		st.push_back(C); dfs(A);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		int A, B, C, D;
		scanf("%d%d%d%d",&A,&B,&C,&D);
		if(C == D) continue;
		adj[A].push_back({B, i});
		adj[B].push_back({A, i});
	}
	for(int i=1;i<=n;i++) {
		if(adj[i].size() % 2) {puts("NIE"); return 0;}
	}
	for(int i=1;i<=n;i++) dfs(i);
	printf("%d\n",ans.size());
	for(int i=0;i<ans.size();i++) {
		printf("%d ",(int)ans[i].size()-1);
		for(auto &T : ans[i]) printf("%d ",T);
		puts("");
	}
}

Compilation message

smi.cpp: In function 'void dfs(int)':
smi.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(cur[C] < adj[C].size()) {
               ^
smi.cpp: In function 'int main()':
smi.cpp:49:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::vector<int> >::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n",ans.size());
                          ^
smi.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ans.size();i++) {
               ^
smi.cpp:37:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
smi.cpp:40:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&A,&B,&C,&D);
                                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5832 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5832 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5832 KB Output is correct
2 Correct 3 ms 5832 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6232 KB Output is correct
2 Correct 0 ms 5964 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6156 KB Output is correct
2 Correct 3 ms 5964 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7028 KB Output is correct
2 Correct 0 ms 5964 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 18708 KB Output is correct
2 Correct 913 ms 132392 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 70716 KB Output is correct
2 Correct 1103 ms 126080 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 103160 KB Output is correct
2 Correct 1246 ms 137024 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 989 ms 124048 KB Output is correct
2 Correct 1269 ms 137024 KB Output is correct