oj.uz

답안 #103586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103586 2019-03-31T19:09:37 Z luciocf 어르신 집배원 (BOI14_postmen) C++14
38 / 100
 500 ms 36480 KB 
#include <bits/stdc++.h>
#define gc getchar

using namespace std;

const int maxn = 5e5+10;

typedef pair<int, int> pii;

int qtd;

bool markEdge[maxn], mark[maxn];

vector<pii> grafo[maxn];
vector<int> ans[maxn];

stack<int> stk;

void dfs(int u)
{
	if (mark[u])
	{
		++qtd;

		while (true)
		{
			int v = stk.top();
			stk.pop();

			mark[v] = 0;
			ans[qtd].push_back(v);

			if (v == u) break;
		}
	}

	for (auto v: grafo[u])
	{
		if (!markEdge[v.second])
		{
			mark[u] = 1;
			stk.push(u);
			markEdge[v.second] = 1;

			dfs(v.first);
		}
	}
}

inline int scan(void)
{
	int n = 0, x = gc(), s =1;

	for (;x<'0'||x>'9';x=gc()) if(x=='-') s=-1;
	for (;x>='0'&&x<='9';x=gc()) n = (n<<3) + (n<<1) + x-'0';
	return n;
}

int main(void)
{
	int n, m;
	n = scan(), m = scan();

	for (int i = 1; i <= m; i++)
	{
		int u, v;
		u = scan(), v = scan();

		grafo[u].push_back({v, i});
		grafo[v].push_back({u, i});
	}

	dfs(1);

	for (int i = 1; i <= qtd; i++)
	{
		printf("%d", ans[i][0]);
		for (int j = 1; j < ans[i].size(); j++)
			printf(" %d", ans[i][j]);
		printf("\n");
	}
}

Compilation message

postmen.cpp: In function 'int scan()':
postmen.cpp:52:23: warning: variable 's' set but not used [-Wunused-but-set-variable]
  int n = 0, x = gc(), s =1;
                       ^
postmen.cpp: In function 'int main()':
postmen.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < ans[i].size(); j++)
                   ~~^~~~~~~~~~~~~~~
postmen.cpp:61:6: warning: variable 'n' set but not used [-Wunused-but-set-variable]
  int n, m;
      ^

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 23 ms 23856 KB Output is correct
4 Correct 21 ms 24140 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 20 ms 24320 KB Output is correct
7 Correct 26 ms 25472 KB Output is correct
8 Correct 25 ms 24116 KB Output is correct
9 Correct 144 ms 34624 KB Output is correct
10 Correct 29 ms 24040 KB Output is correct
11 Correct 18 ms 24040 KB Output is correct
12 Correct 96 ms 34912 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 23 ms 24192 KB Output is correct
5 Correct 24 ms 23872 KB Output is correct
6 Correct 23 ms 24276 KB Output is correct
7 Correct 26 ms 25520 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 106 ms 34472 KB Output is correct
10 Correct 21 ms 24044 KB Output is correct
11 Correct 22 ms 24112 KB Output is correct
12 Correct 80 ms 34912 KB Output is correct
13 Correct 86 ms 36372 KB Output is correct
14 Correct 80 ms 31992 KB Output is correct
15 Execution timed out 1082 ms 35412 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 25 ms 23808 KB Output is correct
4 Correct 26 ms 24168 KB Output is correct
5 Correct 21 ms 23936 KB Output is correct
6 Correct 22 ms 24320 KB Output is correct
7 Correct 25 ms 25600 KB Output is correct
8 Correct 19 ms 24064 KB Output is correct
9 Correct 95 ms 34552 KB Output is correct
10 Correct 25 ms 24064 KB Output is correct
11 Correct 19 ms 24064 KB Output is correct
12 Correct 67 ms 34896 KB Output is correct
13 Correct 88 ms 36480 KB Output is correct
14 Correct 81 ms 32048 KB Output is correct
15 Execution timed out 1075 ms 35388 KB Time limit exceeded
16 Halted 0 ms 0 KB -