Submission #30081

#	Time	Username	Problem	Language	Result	Execution time	Memory
30081		tlwpdus	Untitled (POI11_smi)	C++11	100 / 100	1309 ms	94520 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

int n, m, p;
vector<pii> lis[100100];
bool chk[1000100], visit[100100];
int idx[100100];
vector<int> ans[1000100];

stack<int> st;
void dfs(int here) {
	visit[here] = 1;
	for (;idx[here]<lis[here].size();) {
		pii tmp = lis[here][idx[here]]; idx[here]++;
		int there = tmp.second;
		if (chk[tmp.first]) continue;
		chk[tmp.first] = 1;
		dfs(there);
	}
	st.push(here);
}

bool good[100100];
stack<int> tt;
void add() {
	while(!st.empty()) {
		int here = st.top(); st.pop();
		if (good[here]) {
			ans[p].push_back(here);
			while(tt.top()!=here) {
				ans[p].push_back(tt.top()); good[tt.top()] = 0; tt.pop();
			}
			ans[p].push_back(here); p++;
		}
		else {
			good[here] = 1;
			tt.push(here);
		}
	}
	if (tt.size()>1) printf("SIBAL\n");
	while(!tt.empty()) tt.pop();
}

int main() {
	int i;

	scanf("%d%d",&n,&m);
	for (i=0;i<m;i++) {
		int a, b, s, t;
		scanf("%d%d%d%d",&a,&b,&s,&t); --a; --b;
		if (s^t) {
			lis[a].push_back(pii(i,b));
			lis[b].push_back(pii(i,a));
		}
	}
	for (i=0;i<n;i++) {
		if (lis[i].size()%2) {
			printf("NIE\n");
			return 0;
		}
	}
	for (i=0;i<n;i++) {
		if (visit[i]) continue;
		dfs(i);
		add();
	}
	printf("%d\n",p);
	for (i=0;i<p;i++) {
		printf("%d ",(int)ans[i].size()-1);
		for (int &v : ans[i]) printf("%d ",v+1);
		printf("\n");
	}

    return 0;
}

Compilation message (stderr)

smi.cpp: In function 'void dfs(int)':
smi.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (;idx[here]<lis[here].size();) {
                 ^
smi.cpp: In function 'int main()':
smi.cpp:50: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:53: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,&s,&t); --a; --b;
                                ^

• 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