oj.uz

Submission #977421

# Submission time Handle Problem Language Result Execution time Memory
977421 2024-05-07T23:54:48 Z mariaclara Toy Train (IOI17_train) C++17
0 / 100
 6 ms 1372 KB 
#include "train.h"
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pii;
const int INF = 1e9+10;
const ll LINF = 1e18+10;
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define mk make_pair
#define pb push_back
#define f first 
#define s second

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n = sz(a), m = sz(u); 
	vector<int> ans(n,1), grau(n);
	vector<vector<int>> edges(n);

	for(int i = 0; i < m; i++) 
		edges[v[i]].pb(u[i]), grau[u[i]]++;

	while(1) {
		bool ok = 0;
		vector<int> at_grau(n);
		vector<bool> vis(n);
		queue<int> fila;

		for(int i = 0; i < n; i++) {
			if(r[i] and ans[i]) fila.push(i);
			at_grau[i] = grau[i];
		}

		while(!fila.empty()) {
			int x = fila.front();
			fila.pop();

			if(vis[x]) continue;
			vis[x] = 1;

			for(int viz : edges[x]) {
				at_grau[viz]--;
				if(at_grau[viz] == 0 or a[viz]) fila.push(viz);
			}
		}

		for(int i = 0; i < n; i++) {
			if(ans[i] and !vis[i]) ok = 1;
			if(!vis[i]) ans[i] = 0, fila.push(i);
			at_grau[i] = grau[i];
		}

		while(!fila.empty()) {
			int x = fila.front();
			fila.pop();

			if(vis[x]) continue;
			if(ans[x]) ok = 1;
			vis[x] = 1;
			ans[x] = 0;

			for(int viz : edges[x]) {
				at_grau[viz]--;
				if(at_grau[viz] == 0 or !a[viz]) fila.push(viz);
			}
		}

		if(!ok) break;
	}

	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 856 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 344 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1372 KB Output is correct
2 Correct 6 ms 1372 KB Output is correct
3 Correct 6 ms 1372 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 3 ms 964 KB 3rd lines differ - on the 3730th token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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