Submission #84190

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
84190	2018-11-13T21:09:21 Z	nikolapesic2802	Garbage (POI11_smi)	C++14	100 / 100	732 ms	64144 KB

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 100005;
 
#include <stdio.h>
#include <stdlib.h>
static char _buffer[1 << 19];
static int _currentChar = 0;
static int _charsNumber = 0;
 
static inline int _read() {
	if (_charsNumber < 0) {
		exit(1);
	}
	if (!_charsNumber || _currentChar == _charsNumber) {
		_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), stdin);
		_currentChar = 0;
	}
	if (_charsNumber <= 0) {
		return -1;
	}
	return _buffer[_currentChar++];
}
 
static inline int _readInt() {
	int c, x, s;
	c = _read();
	while (c <= 32) c = _read();
	x = 0;
	s = 1;
	if (c == '-') {
		s = -1;
		c = _read();
	}
	while (c > 32) {
		x *= 10;
		x += c - '0';
		c = _read();
	}
	if (s < 0) x = -x;
	return x;
}
 
int n, m;
vector<pi> gph[MAXN];
int ptr[MAXN], vis[1000005];
 
vector<vector<int>> pth;
vector<int> lis;
 
void dfs(int x){
	while(1){
		lis.push_back(x);
		while(ptr[x] < gph[x].size() && vis[gph[x][ptr[x]].second]){
			ptr[x]++;
		}
		if(ptr[x] == gph[x].size()) break;
		int nxt = gph[x][ptr[x]].first;
		vis[gph[x][ptr[x]].second] = 1;
		x = nxt;
	}
}
 
bool instk[MAXN];
 
int main(){
	n = _readInt();
	m = _readInt();
	for(int i=0; i<m; i++){
		int s, e, x, y;
		s = _readInt();
		e = _readInt();
		x = _readInt();
		y = _readInt();
		if(x == y) continue;
		gph[s].push_back(pi(e, i));
		gph[e].push_back(pi(s, i));
	}
	for(int i=1; i<=n; i++){
		if(gph[i].size() & 1){
			puts("NIE");
			return 0;
		}
	}
	for(int i=1; i<=n; i++){
		if(gph[i].empty()) continue;
		lis.clear();
		dfs(i);
		stack<int> stk;
		for(auto &i : lis){
			if(instk[i]){
				vector<int> v = {i};
				while(!stk.empty() && stk.top() != i){
					v.push_back(stk.top());
					instk[stk.top()] = 0;
					stk.pop();
				}
				v.push_back(i);
				pth.push_back(v);
			}
			else{
				stk.push(i);
				instk[i] = 1;
			}
		}
	}
	printf("%d\n", pth.size());
	for(auto &i : pth){
		printf("%d ", i.size() - 1);
		for(auto &j : i) printf("%d ", j);
		puts("");
	}
}

Compilation message

smi.cpp: In function 'void dfs(int)':
smi.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr[x] < gph[x].size() && vis[gph[x][ptr[x]].second]){
         ~~~~~~~^~~~~~~~~~~~~~~
smi.cpp:60:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr[x] == gph[x].size()) break;
      ~~~~~~~^~~~~~~~~~~~~~~~
smi.cpp: In function 'int main()':
smi.cpp:110:27: 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", pth.size());
                 ~~~~~~~~~~^
smi.cpp:112:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d ", i.size() - 1);
                 ~~~~~~~~~~~~^

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2812 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2812 KB	Output is correct
2	Correct	4 ms	2812 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3188 KB	Output is correct
2	Correct	4 ms	3188 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3228 KB	Output is correct
2	Correct	4 ms	3228 KB	Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	9640 KB	Output is correct
2	Correct	424 ms	50004 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	259 ms	50004 KB	Output is correct
2	Correct	413 ms	50004 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	483 ms	50004 KB	Output is correct
2	Correct	529 ms	52408 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	732 ms	52408 KB	Output is correct
2	Correct	569 ms	64144 KB	Output is correct