oj.uz

답안 #68888

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68888 2018-08-19T03:16:35 Z MatheusLealV 어르신 집배원 (BOI14_postmen) C++17
55 / 100
 500 ms 89956 KB 
#include <bits/stdc++.h>
#define N 500050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, m, block[N], cnt = 0, usado[N], prox[N], id = 1;

vector<pii> grafo[N];

vector<int> path[N];

bool dfs(int x, int ini, int f)
{
	//cout<<"DFS "<<x<<"\n";
	usado[x] = id;

	for(auto v: grafo[x])
	{
		if(v.f == ini and !block[v.s])
		{
			block[v.s] = 1;

			// cout<<"PROX "<<x<<" "<<"-1\n";

			prox[x] = -1;

			return true;
		}

		if(usado[v.f] == id or block[v.s]) continue;

		//cout<<"DFS "<<x<<" to "<<v.f<<"\n";

		if(dfs(v.f, ini, f))
		{
			prox[x] = v.f;

			// cout<<"PROX "<<x<<" "<<v.f<<"\n";

			block[v.s] = 1;

			return true;
		}
	}

	return false;
}

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

	cin>>n>>m;

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

		grafo[a].push_back({b, i});

		grafo[b].push_back({a, i});
	}

	for(int x = 1; x <= n; x++)
	{
		for(auto v: grafo[x])
		{
			if(block[v.s]) continue;

			++id;

			usado[x] = id;

			block[v.s] = 1;

			path[cnt].push_back(x);

			if(dfs(v.f, x, cnt))
			{
				int u = v.f;

				while(u != -1)
				{					
					path[cnt].push_back(u);

					u = prox[u];
				}
				++ cnt;
			}
		}
	}

	for(int i = 0; i < cnt; i++)
	{
		for(auto x: path[i]) cout<<x<<" ";

		cout<<"\n";
	}
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23936 KB Output is correct
2 Correct 27 ms 23856 KB Output is correct
3 Correct 23 ms 23808 KB Output is correct
4 Correct 22 ms 24064 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 26 ms 24056 KB Output is correct
7 Correct 40 ms 24576 KB Output is correct
8 Correct 19 ms 24064 KB Output is correct
9 Correct 178 ms 27232 KB Output is correct
10 Correct 20 ms 24064 KB Output is correct
11 Correct 26 ms 23976 KB Output is correct
12 Correct 111 ms 27768 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 21 ms 23812 KB Output is correct
3 Correct 20 ms 23808 KB Output is correct
4 Correct 22 ms 24052 KB Output is correct
5 Correct 27 ms 23912 KB Output is correct
6 Correct 25 ms 24064 KB Output is correct
7 Correct 35 ms 24588 KB Output is correct
8 Correct 22 ms 24184 KB Output is correct
9 Correct 172 ms 27204 KB Output is correct
10 Correct 27 ms 23992 KB Output is correct
11 Correct 19 ms 24064 KB Output is correct
12 Correct 117 ms 27752 KB Output is correct
13 Correct 94 ms 37464 KB Output is correct
14 Correct 121 ms 33012 KB Output is correct
15 Correct 87 ms 29200 KB Output is correct
16 Correct 109 ms 37360 KB Output is correct
17 Correct 162 ms 29536 KB Output is correct
18 Correct 125 ms 31456 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23784 KB Output is correct
2 Correct 23 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 24 ms 24064 KB Output is correct
5 Correct 23 ms 23936 KB Output is correct
6 Correct 22 ms 24040 KB Output is correct
7 Correct 30 ms 24508 KB Output is correct
8 Correct 19 ms 24168 KB Output is correct
9 Correct 182 ms 26976 KB Output is correct
10 Correct 22 ms 24064 KB Output is correct
11 Correct 20 ms 24064 KB Output is correct
12 Correct 100 ms 27640 KB Output is correct
13 Correct 97 ms 37104 KB Output is correct
14 Correct 103 ms 32796 KB Output is correct
15 Correct 95 ms 28908 KB Output is correct
16 Correct 116 ms 37108 KB Output is correct
17 Correct 142 ms 29176 KB Output is correct
18 Correct 89 ms 30968 KB Output is correct
19 Execution timed out 562 ms 89956 KB Time limit exceeded
20 Halted 0 ms 0 KB -