답안 #53441 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
53441	2018-06-30T03:40:39 Z	ainta	장난감 기차 (IOI17_train)	C++17	0 / 100	2000 ms	1948 KB

train

#include "train.h"
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int n, m, D[5010], U[5010], InQ[5010], C[5010];
vector<int>E[5010], F[5010];

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = a.size();
	m = u.size();
	int i, j, k;
	for (i = 0; i < n; i++) {
		if (r[i] == 1)D[i] = 1;
		else D[i] = 0;
	}
	queue<int>Q;
	for (i = 0; i < m; i++) {
		E[u[i]].push_back(v[i]);
		F[v[i]].push_back(u[i]);
	}
	for (i = 0; i < n; i++) {
		if (a[i] == 1) {
			for (auto &t : E[i]) {
				if (D[i] < D[t] + r[i]) {
					Q.push(i);
					InQ[i] = 1;
					break;
				}
			}
		}
		if (a[i] == 0) {
			int ck = 0;
			for (auto &t : E[i]) {
				if (D[i] >= D[t] + r[i])C[i]++;
			}
			if (C[i] == 0) {
				Q.push(i);
				InQ[i] = 1;
			}
		}
	}
	while (!Q.empty()) {
		int x = Q.front();
		Q.pop();
		InQ[x] = 0;
		if (a[x] == 1) {
			int d = -1e9;
			for (auto &t : E[x]) {
				d = max(d, D[t] + r[x]);
			}
			d = min(d, n);
			if (D[x] == d)continue;
			for (auto &t : F[x]) {
				if (a[t] == 1) {
					if (D[t] < r[t] + d) {
						if (!InQ[t]) {
							InQ[t] = 1;
							Q.push(t);
						}
					}
				}
				else {
					if (D[t] >= r[t] + D[x] && D[t] < r[t] + d) {
						C[t]--;
						if (!C[t]) {
							if (!InQ[t]) {
								InQ[t] = 1;
								Q.push(t);
							}
						}
					}
				}
			}
			D[x] = d;
		}
		else {
			int d = 1e9;
			for (auto &t : E[x]) {
				d = min(d, D[t] + r[x]);
			}
			d = min(d, n);
			if (D[x] == d)continue;
			C[x] = 0;
			for (auto &t : E[x]) {
				if (d >= D[t] + r[x])C[x]++;
			}
			for (auto &t : F[x]) {
				if (a[t] == 1) {
					if (D[t] < r[t] + d) {
						if (!InQ[t]) {
							InQ[t] = 1;
							Q.push(t);
						}
					}
				}
				else {
					if (D[t] >= r[t] + D[x] && D[t] < r[t] + d) {
						C[t]--;
						if (!C[t]) {
							if (!InQ[t]) {
								InQ[t] = 1;
								Q.push(t);
							}
						}
					}
				}
			}
			D[x] = d;
		}
	}
	vector<int>res(n);
	for (i = 0; i < n; i++) {
		if (D[i] >= n)res[i] = 1;
		else res[i] = 0;
	}
	return res;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:35:8: warning: unused variable 'ck' [-Wunused-variable]
    int ck = 0;
        ^~
train.cpp:14:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k;
         ^
train.cpp:14:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	245 ms	1144 KB	3rd lines differ - on the 26th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1144 KB	Output is correct
2	Correct	2 ms	1144 KB	Output is correct
3	Correct	2 ms	1144 KB	Output is correct
4	Correct	2 ms	1144 KB	Output is correct
5	Correct	2 ms	1144 KB	Output is correct
6	Correct	3 ms	1144 KB	Output is correct
7	Correct	3 ms	1144 KB	Output is correct
8	Correct	3 ms	1144 KB	Output is correct
9	Incorrect	3 ms	1144 KB	3rd lines differ - on the 13th token, expected: '1', found: '0'
10	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	98 ms	1740 KB	Output is correct
2	Correct	173 ms	1748 KB	Output is correct
3	Correct	223 ms	1752 KB	Output is correct
4	Correct	1200 ms	1948 KB	Output is correct
5	Correct	1444 ms	1948 KB	Output is correct
6	Correct	37 ms	1948 KB	Output is correct
7	Correct	570 ms	1948 KB	Output is correct
8	Correct	828 ms	1948 KB	Output is correct
9	Correct	22 ms	1948 KB	Output is correct
10	Correct	1063 ms	1948 KB	Output is correct
11	Correct	517 ms	1948 KB	Output is correct
12	Correct	15 ms	1948 KB	Output is correct
13	Execution timed out	2054 ms	1948 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-