Submission #120441

#	Time	Username	Problem	Language	Result	Execution time	Memory
120441		popovicirobert	Untitled (POI11_smi)	C++14	100 / 100	1187 ms	129892 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x)) 

using namespace std;

const int MAXN = (int) 1e5;
const int MAXM = (int) 1e6;

vector < pair <int, int> > g[MAXN + 1];
bool instk[MAXN + 1], vis[MAXM + 1];

vector < vector <int> > sol;
stack <int> stk;

void dfs(int nod) {
	if(instk[nod]) {
		vector <int> cur;
		cur.push_back(nod);
		while(stk.top() != nod) {
			instk[stk.top()] = 0;
			cur.push_back(stk.top());
			instk[stk.top()] = 0;
			stk.pop();
		}
		instk[nod] = 0;
		stk.pop();
		sol.push_back(cur);
	}

	while(g[nod].size()) {
		auto cur = g[nod].back();
		g[nod].pop_back();
		if(vis[cur.second]) 
			continue;
		vis[cur.second] = instk[nod] = 1;
		stk.push(nod);
		dfs(cur.first);
	}
}

int main() {
	//ifstream cin("A.in");
	//ofstream cout("A.out");
	int i, n, m; 
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> m;
	for(i = 1; i <= m; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		if(c != d) {
			g[a].push_back({b, i});
			g[b].push_back({a, i});
		}
	}

	for(i = 1; i <= n; i++) {
		if(g[i].size() & 1) {
			cout << "NIE";
			return 0;
		}
	}

	for(i = 1; i <= n; i++) {
		dfs(i);
	}

	cout << sol.size() << "\n";
	for(i = 0; i < sol.size(); i++) {
		cout << sol[i].size() << " ";
		for(auto it : sol[i]) {
			cout << it << " ";
		}
		cout << sol[i][0] << "\n";
	}
	return 0;
}

Compilation message (stderr)

smi.cpp: In function 'int main()':
smi.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < sol.size(); i++) {
             ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10