답안 #790162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790162	2023-07-22T11:28:03 Z	NothingXD	장난감 기차 (IOI17_train)	C++17	11 / 100	1259 ms	1804 KB

train

#include "train.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e4 + 10;

int n, m;
ll h[maxn];
vector<pair<pii,int>> edge;
vector<int> g[maxn];
bool vis[maxn];

void dfs(int v){
	//debug(v);
	vis[v] = true;
	for (auto u: g[v]){
		if (!vis[u]) dfs(u);
	}
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = a.size();
	m = u.size();
	edge.clear();
	for (int i = 0; i < n; i++){
		g[i].clear();
	}
	for (int i = 0; i < m; i++){
		v[i] += n;
		edge.push_back({{v[i], u[i]}, 1});
		v[i] -= n;
		g[v[i]].push_back(u[i]);
	}
	for (int i = 0; i < n; i++){
		if (r[i]){
			edge.push_back({{i, i+n}, -(n+1)});
			//debug(i, i+n, -n-1);
		}
		else{
			edge.push_back({{i, i+n}, 0});
			//debug(i, i+n, 0);
		}
	}
	memset(h, 0, sizeof h);
	memset(vis, false, sizeof vis);
	for (int i = 1; i <= 4*n; i++){
		for (auto x: edge){
			if (i >= 2*n && h[x.F.S] > h[x.F.F] + x.S){
				int u = x.F.S;
				if (u >= n) u -= n;
				if (!vis[u]) dfs(u);
			}
			h[x.F.S] = min(h[x.F.S], h[x.F.F] + x.S);
		}
	}
	vector<int> ans(n);
	for (int i = 0; i < n; i++){
		ans[i] = vis[i];
	}
	return ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	701 ms	1572 KB	Output is correct
2	Correct	685 ms	1568 KB	Output is correct
3	Correct	711 ms	1552 KB	Output is correct
4	Correct	1259 ms	1576 KB	Output is correct
5	Correct	1124 ms	1776 KB	Output is correct
6	Correct	767 ms	1748 KB	Output is correct
7	Correct	1126 ms	1748 KB	Output is correct
8	Correct	752 ms	1724 KB	Output is correct
9	Correct	682 ms	1656 KB	Output is correct
10	Correct	1082 ms	1688 KB	Output is correct
11	Correct	1098 ms	1680 KB	Output is correct
12	Correct	666 ms	1640 KB	Output is correct
13	Correct	914 ms	1796 KB	Output is correct
14	Correct	871 ms	1748 KB	Output is correct
15	Correct	867 ms	1804 KB	Output is correct
16	Correct	1018 ms	1792 KB	Output is correct
17	Correct	931 ms	1800 KB	Output is correct
18	Correct	439 ms	1392 KB	Output is correct