Submission #9191443

Source Code Expand

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

typedef pair<int, int> pii;
const int N = 1e5 + 100;

int n, m, t, x[N], y[N];
bool way[N];
vector<pii> vec[N];
vector<int> dp[N];
mt19937 LODB(chrono::steady_clock::now().time_since_epoch().count());

int last[N];

bool ok() {
	for (int i = 0; i < n; i++)
		last[i] = dp[i].size();
	for (int i = m - 1; ~i; i--) {
		int X = x[i], Y = y[i];
		int dex_y = --last[Y];
		int dex_x = --last[X];
		
		dp[X][dex_x] = (dex_x == (dp[X].size() - 1)? X: dp[X][dex_x + 1]);
		dp[Y][dex_y] = (dex_y == (dp[Y].size() - 1)? Y: dp[Y][dex_y + 1]);

		if (way[i]) {
			if (dex_x == (vec[X].size() - 1))
				dp[Y][dex_y] = X;
			else
				dp[Y][dex_y] = dp[X][dex_x + 1];
		}

		else {
			if (dex_y == (vec[Y].size() - 1))
				dp[X][dex_x] = Y;
			else
				dp[X][dex_x] = dp[Y][dex_y + 1];
		}
	}
	int res = (dp[0].size()? dp[0][0]: 0);
	for (int i = 1; i < n; i++)
		if ((dp[i].size()? dp[i][0]: i) != res)
			return false;
	return true;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m >> t;
	for (int i = 0; i < m; i++) {
		cin >> x[i] >> y[i];
		vec[--x[i]].push_back(pii(i, --y[i]));
		vec[y[i]].push_back(pii(i, x[i]));
		dp[x[i]].push_back(0);
		dp[y[i]].push_back(0);
	}
	t &= 1;
	int tof = 500;
	while (tof--) {
		for (int i = 0; i < m; i++)
			way[i] = LODB() & 1;
		
		if (ok() == t) {
			for (int i = 0; i < m; i++)
				cout << (way[i]? '^': 'v');
			return 0;
		}
	}
	cout << -1;
}

Submission Info

Submission Time
Task E - Balancing Network
User LODB
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1517 Byte
Status WA
Exec Time 2104 ms
Memory 13440 KiB

Judge Result

Set Name Sample Uniforming Non-uniforming
Score / Max Score 0 / 0 0 / 800 0 / 800
Status
AC × 4
AC × 31
WA × 19
TLE × 5
AC × 17
WA × 8
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 00-sample-04.txt
Uniforming 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 01-47.txt, 01-48.txt, 01-49.txt, 01-50.txt, 01-51.txt, 01-52.txt, 01-53.txt, 01-54.txt, 01-55.txt
Non-uniforming 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 3 ms 4992 KiB
00-sample-02.txt AC 3 ms 4992 KiB
00-sample-03.txt AC 3 ms 4992 KiB
00-sample-04.txt AC 3 ms 4992 KiB
01-01.txt AC 3 ms 4992 KiB
01-02.txt AC 3 ms 5120 KiB
01-03.txt AC 3 ms 4992 KiB
01-04.txt AC 3 ms 4992 KiB
01-05.txt AC 3 ms 4992 KiB
01-06.txt AC 3 ms 4992 KiB
01-07.txt AC 3 ms 4992 KiB
01-08.txt AC 21 ms 9320 KiB
01-09.txt AC 21 ms 9056 KiB
01-10.txt AC 21 ms 9072 KiB
01-11.txt AC 3 ms 4992 KiB
01-12.txt AC 3 ms 4992 KiB
01-13.txt AC 3 ms 4992 KiB
01-14.txt AC 3 ms 4992 KiB
01-15.txt AC 3 ms 4992 KiB
01-16.txt AC 3 ms 4992 KiB
01-17.txt AC 21 ms 8808 KiB
01-18.txt AC 21 ms 8776 KiB
01-19.txt AC 21 ms 9460 KiB
01-20.txt AC 11 ms 5120 KiB
01-21.txt WA 11 ms 5120 KiB
01-22.txt WA 10 ms 5120 KiB
01-23.txt AC 11 ms 5120 KiB
01-24.txt WA 11 ms 5120 KiB
01-25.txt WA 10 ms 5120 KiB
01-26.txt WA 697 ms 10880 KiB
01-27.txt WA 695 ms 8832 KiB
01-28.txt WA 690 ms 8820 KiB
01-29.txt AC 35 ms 5120 KiB
01-30.txt AC 35 ms 5120 KiB
01-31.txt AC 35 ms 5120 KiB
01-32.txt AC 44 ms 5248 KiB
01-33.txt AC 43 ms 5248 KiB
01-34.txt AC 43 ms 5248 KiB
01-35.txt WA 850 ms 10752 KiB
01-36.txt WA 748 ms 11520 KiB
01-37.txt WA 734 ms 10612 KiB
01-38.txt AC 425 ms 9088 KiB
01-39.txt WA 392 ms 8704 KiB
01-40.txt WA 390 ms 9336 KiB
01-41.txt AC 425 ms 9088 KiB
01-42.txt WA 394 ms 8704 KiB
01-43.txt WA 388 ms 9336 KiB
01-44.txt WA 445 ms 9088 KiB
01-45.txt AC 446 ms 9088 KiB
01-46.txt WA 389 ms 8704 KiB
01-47.txt WA 389 ms 8704 KiB
01-48.txt AC 1948 ms 13312 KiB
01-49.txt TLE 2080 ms 11520 KiB
01-50.txt TLE 2079 ms 11392 KiB
01-51.txt WA 1769 ms 13440 KiB
01-52.txt TLE 2104 ms 11392 KiB
01-53.txt TLE 2050 ms 11392 KiB
01-54.txt WA 1803 ms 13440 KiB
01-55.txt TLE 2070 ms 11392 KiB
02-01.txt AC 3 ms 4992 KiB
02-02.txt AC 671 ms 8916 KiB
02-03.txt WA 672 ms 9192 KiB
02-04.txt WA 682 ms 8672 KiB
02-05.txt WA 674 ms 8556 KiB
02-06.txt WA 675 ms 8804 KiB
02-07.txt WA 680 ms 9472 KiB
02-08.txt WA 681 ms 9344 KiB
02-09.txt WA 680 ms 8832 KiB
02-10.txt WA 684 ms 9472 KiB
02-11.txt AC 90 ms 9856 KiB
02-12.txt AC 55 ms 8960 KiB
02-13.txt AC 133 ms 8704 KiB
02-14.txt AC 30 ms 8960 KiB
02-15.txt AC 27 ms 9088 KiB
02-16.txt AC 32 ms 9472 KiB
02-17.txt AC 31 ms 9728 KiB
02-18.txt AC 25 ms 9472 KiB
02-19.txt AC 27 ms 9728 KiB
02-20.txt AC 29 ms 9856 KiB
02-21.txt AC 41 ms 10112 KiB
02-22.txt AC 58 ms 11264 KiB
02-23.txt AC 23 ms 8704 KiB
02-24.txt AC 24 ms 8832 KiB
02-25.txt AC 25 ms 8832 KiB