oj.uz

Submission #790165

# Submission time Handle Problem Language Result Execution time Memory
790165 2023-07-22T11:29:11 Z NothingXD Toy Train (IOI17_train) C++17
11 / 100
 1223 ms 1748 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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 580 ms 1228 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
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 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 1652 KB Output is correct
2 Correct 794 ms 1560 KB Output is correct
3 Correct 815 ms 1652 KB Output is correct
4 Incorrect 1099 ms 1576 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 1388 KB Output is correct
2 Correct 842 ms 1632 KB Output is correct
3 Correct 1216 ms 1748 KB Output is correct
4 Correct 1219 ms 1748 KB Output is correct
5 Correct 1180 ms 1748 KB Output is correct
6 Correct 1027 ms 1736 KB Output is correct
7 Correct 1039 ms 1704 KB Output is correct
8 Correct 1098 ms 1680 KB Output is correct
9 Correct 880 ms 1640 KB Output is correct
10 Correct 860 ms 1748 KB Output is correct
11 Correct 729 ms 1748 KB Output is correct
12 Correct 801 ms 1748 KB Output is correct
13 Correct 1223 ms 1744 KB Output is correct
14 Correct 900 ms 1680 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1073 ms 1568 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 580 ms 1228 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -