Submission #790162

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790162	2023-07-22T11:28:03 Z	NothingXD	Toy Train (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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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