oj.uz

Submission #321057

# Submission time Handle Problem Language Result Execution time Memory
321057 2020-11-10T19:24:01 Z VodkaInTheJar Garbage (POI11_smi) C++14
10 / 100
 772 ms 262148 KB 
#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)
		{
			assert(j <= n);
			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.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB cykl nie jest prosty

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2796 KB Integer 1010 violates the range [0, 500]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2924 KB Integer 2269 violates the range [0, 1200]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2924 KB Integer 525 violates the range [0, 200]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 3180 KB Integer 4483 violates the range [0, 2000]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 772 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 310 ms 34808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 502 ms 48484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 623 ms 58980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -