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
#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;
}
# 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 -
# 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 -
# 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
# Verdict Execution time Memory Grader output
1 Incorrect 831 ms 1420 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 983 ms 1580 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 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 -