Submission #115960

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
115960	2019-06-10T04:54:20 Z	Mahdi_Jfri	Senior Postmen (BOI14_postmen)	C++14	55 / 100	500 ms	55296 KB

postmen

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 5e5 + 20;

vector<int> adj[maxn] , path;

int from[maxn] , to[maxn];

bool visited[maxn];

void dfs(int v)
{
	while(!adj[v].empty())
	{
		int e = adj[v].back() , u = from[e] ^ to[e] ^ v;
		adj[v].pop_back();

		if(visited[e])
			continue;

		visited[e] = 1;
		dfs(u);
	}
	path.pb(v);
}

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

	int n , m;
	cin >> n >> m;

	for(int i = 0; i < m; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;

		adj[a].pb(i);
		adj[b].pb(i);

		from[i] = a , to[i] = b;
	}

	dfs(0);

	vector<int> tmp;
	memset(visited , 0 , sizeof visited);
	for(auto v : path)
	{
		if(visited[v])
		{
			while(tmp.back() != v)
				cout << tmp.back() + 1 << " " , visited[tmp.back()] = 0 , tmp.pop_back();
			tmp.pop_back();
			cout << v + 1 << endl;
		}

		tmp.pb(v);
		visited[v] = 1;
	}
}

Subtask #1

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12544 KB	Output is correct
2	Correct	11 ms	12544 KB	Output is correct
3	Correct	12 ms	12544 KB	Output is correct
4	Correct	17 ms	12800 KB	Output is correct
5	Correct	13 ms	12672 KB	Output is correct
6	Correct	13 ms	12928 KB	Output is correct
7	Correct	19 ms	13620 KB	Output is correct
8	Correct	12 ms	12800 KB	Output is correct
9	Correct	53 ms	18416 KB	Output is correct
10	Correct	16 ms	12800 KB	Output is correct
11	Correct	15 ms	12800 KB	Output is correct
12	Correct	61 ms	18536 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	12544 KB	Output is correct
2	Correct	13 ms	12544 KB	Output is correct
3	Correct	14 ms	12576 KB	Output is correct
4	Correct	15 ms	12800 KB	Output is correct
5	Correct	13 ms	12672 KB	Output is correct
6	Correct	16 ms	12852 KB	Output is correct
7	Correct	19 ms	13568 KB	Output is correct
8	Correct	12 ms	12800 KB	Output is correct
9	Correct	57 ms	18416 KB	Output is correct
10	Correct	15 ms	12800 KB	Output is correct
11	Correct	16 ms	12800 KB	Output is correct
12	Correct	67 ms	18592 KB	Output is correct
13	Correct	118 ms	21232 KB	Output is correct
14	Correct	130 ms	18772 KB	Output is correct
15	Correct	160 ms	19936 KB	Output is correct
16	Correct	91 ms	21104 KB	Output is correct
17	Correct	155 ms	17140 KB	Output is correct
18	Correct	137 ms	19228 KB	Output is correct

Subtask #3

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	12544 KB	Output is correct
2	Correct	12 ms	12544 KB	Output is correct
3	Correct	14 ms	12596 KB	Output is correct
4	Correct	15 ms	12800 KB	Output is correct
5	Correct	15 ms	12672 KB	Output is correct
6	Correct	13 ms	12928 KB	Output is correct
7	Correct	20 ms	13568 KB	Output is correct
8	Correct	12 ms	12800 KB	Output is correct
9	Correct	51 ms	18416 KB	Output is correct
10	Correct	15 ms	12800 KB	Output is correct
11	Correct	19 ms	12800 KB	Output is correct
12	Correct	63 ms	18544 KB	Output is correct
13	Correct	108 ms	21208 KB	Output is correct
14	Correct	146 ms	18672 KB	Output is correct
15	Correct	155 ms	19784 KB	Output is correct
16	Correct	91 ms	21080 KB	Output is correct
17	Correct	156 ms	17212 KB	Output is correct
18	Correct	132 ms	19312 KB	Output is correct
19	Execution timed out	581 ms	55296 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-