Submission #321053

#	Time	Username	Problem	Language	Result	Execution time	Memory
321053		VodkaInTheJar	Untitled (POI11_smi)	C++14	10 / 100	751 ms	262148 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

const int maxn = 1e5 + 3; 

int n, m; 
vector <pair <int, int> > adj[maxn];
void read()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b, s, t; 
		cin >> a >> b >> s >> t;
		
		if (s == t)
		continue;
		
		adj[a].push_back({b, i});
		adj[b].push_back({a, i});
	}
}

int pos[maxn];
bool used[maxn];
void solve()
{
	for (int i = 1; i <= n; i++)
	if ((int)adj[i].size() % 2 == 1)
	{
		cout << "NIE" << endl;
		return;
	}
	
	vector <vector <int> > ans; 
	for (int i = 1; i <= n; i++)
	{
		if (pos[i] == (int)adj[i].size())
		continue;
		
		vector <int> order;
		stack <int> st; 
		
		st.push(i);
		while (!st.empty())
		{
			int ver = st.top();
			while (pos[ver] < (int)adj[ver].size() && used[adj[ver][pos[ver]].second])
			pos[ver]++;
			
			if (pos[ver] == (int)adj[ver].size())
			{
				order.push_back(ver);
				st.pop();
				continue;
			}
			
			used[adj[ver][pos[ver]].second] = true;
			st.push(adj[ver][pos[ver]].first);
		}

		
		for (int i = 0; i < (int)order.size()-1; )
	    {
		    int j = i + 1;
		    while (j < (int)order.size() && order[j] != order[i])
		    j++;
		
		    vector <int> v;
		    for (int k = i; k < j; k++)
		    v.push_back(order[k]);
		
		    ans.push_back(v);
		    i = j;
	     }
	}

	
	cout << (int)ans.size() << endl;
	for (auto i: ans)
	{
		cout << (int)i.size() << " ";
		for (auto j: i)
		cout << j << " ";
		
		cout << i[0] << endl; 
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	read();
	solve();
}

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