oj.uz

Submission #208725

# Submission time Handle Problem Language Result Execution time Memory
208725 2020-03-12T05:37:13 Z E869120 Senior Postmen (BOI14_postmen) C++14
0 / 100
 500 ms 12856 KB 
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#pragma warning (disable: 4996)

struct Node {
	int to, cap, rev;
};

int N, M, A[1 << 19], B[1 << 19];
vector<Node> X[1 << 19]; int cur[1 << 19];
bool used[1 << 19];

int vec[1 << 19], sz;

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d%d", &A[i], &B[i]);
		X[A[i]].push_back(Node{ B[i], 1, (int)X[B[i]].size() });
		X[B[i]].push_back(Node{ A[i], 1, (int)X[A[i]].size() - 1 });
	}

	int num = M, cnt = 1;
	while (num > 0) {
		while (true) {
			while (cur[cnt] < X[cnt].size() && X[cnt][cur[cnt]].cap == 0) cur[cnt]++;
			if (cur[cnt] < X[cnt].size()) break;
			cnt++;
		}

		int cx = cnt; sz = 0;
		while (true) {
			vec[sz] = cx; sz++;
			int nex = -1, res = -1;
			while (X[cx][cur[cx]].cap == 0) cur[cx]++;
			nex = X[cx][cur[cx]].to;
			res = X[cx][cur[cx]].rev;
			X[cx][cur[cx]].cap = 0;
			X[nex][res].cap = 0;
			num--;
			if (nex == cnt) break;
			cx = nex;
		}
		vec[sz] = cnt; sz++;
		for (int i : vec) used[i] = false;

		vector<int> v1;
		for (int i = 0; i < sz; i++) {
			if (used[vec[i]] == true) {
				vector<int> ret;
				while (true) {
					int cp = v1[v1.size() - 1];
					ret.push_back(cp); used[cp] = false;
					v1.pop_back();
					if (cp == vec[i]) break;
				}
				for (int j = 0; j < ret.size(); j++) { if (j) printf(" "); printf("%d", ret[j]); }
				printf("\n");
			}
			used[vec[i]] = true;
			v1.push_back(vec[i]);
		}
	}
	return 0;
}

Compilation message

postmen.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
postmen.cpp: In function 'int main()':
postmen.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (cur[cnt] < X[cnt].size() && X[cnt][cur[cnt]].cap == 0) cur[cnt]++;
           ~~~~~~~~~^~~~~~~~~~~~~~~
postmen.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (cur[cnt] < X[cnt].size()) break;
        ~~~~~~~~~^~~~~~~~~~~~~~~
postmen.cpp:59:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < ret.size(); j++) { if (j) printf(" "); printf("%d", ret[j]); }
                     ~~^~~~~~~~~~~~
postmen.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12716 KB Output is correct
2 Correct 15 ms 12672 KB Output is correct
3 Correct 17 ms 12672 KB Output is correct
4 Execution timed out 1063 ms 12844 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12724 KB Output is correct
2 Correct 14 ms 12672 KB Output is correct
3 Correct 16 ms 12672 KB Output is correct
4 Execution timed out 1089 ms 12848 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12672 KB Output is correct
2 Correct 14 ms 12672 KB Output is correct
3 Correct 16 ms 12672 KB Output is correct
4 Execution timed out 1088 ms 12856 KB Time limit exceeded
5 Halted 0 ms 0 KB -