oj.uz

Submission #970373

# Submission time Handle Problem Language Result Execution time Memory
970373 2024-04-26T12:48:38 Z GrindMachine Toy Train (IOI17_train) C++17
11 / 100
 1683 ms 50708 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 5e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "train.h"

vector<int> adj[N];
bool edge[N][N];
bool path[N][N];
vector<bool> vis(N);

void dfs1(int u, int r){
	vis[u] = 1;
	path[r][u] = 1;
	trav(v,adj[u]){
		if(vis[v]) conts;
		dfs1(v,r);
	}
}

vector<bool> in_cyc(N);
vector<bool> good(N);

void dfs2(int u, int r){
	vis[u] = 1;
	trav(v,adj[u]){
		if(!good[v]) conts;
		if(vis[v]){
			if(v == r){
				in_cyc[r] = 1;
			}
		}
		else{
			dfs2(v,r);
		}
	}
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> b, std::vector<int> U, std::vector<int> V) {
	int n = sz(a);
	int m = sz(U);

	rep(i,m){
		int u = U[i], v = V[i];
		adj[u].pb(v);
		edge[u][v] = 1;
	}

	vector<int> ans(n,1);
	rep(i,n){
		fill(all(vis),0);
		dfs1(i,i);
	}

	rep(i,n) good[i] = b[i]^1;

	rep(i,n){
		if(!good[i]) conts;
		fill(all(vis),0);
		dfs2(i,i);
	}

	rep(i,n){
		rep(j,n){
			if(path[i][j] and !b[j] and in_cyc[j]){
				ans[i] = 0;
			}
		}
	}

	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 184 ms 49748 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 2652 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 312 ms 50048 KB Output is correct
2 Correct 284 ms 50100 KB Output is correct
3 Correct 249 ms 50000 KB Output is correct
4 Incorrect 1343 ms 50512 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 652 ms 50060 KB Output is correct
2 Correct 263 ms 50004 KB Output is correct
3 Correct 458 ms 50256 KB Output is correct
4 Correct 521 ms 50068 KB Output is correct
5 Correct 586 ms 50256 KB Output is correct
6 Correct 529 ms 50256 KB Output is correct
7 Correct 544 ms 50012 KB Output is correct
8 Correct 455 ms 49956 KB Output is correct
9 Correct 67 ms 50000 KB Output is correct
10 Correct 834 ms 50268 KB Output is correct
11 Correct 875 ms 50480 KB Output is correct
12 Correct 792 ms 50236 KB Output is correct
13 Correct 902 ms 50308 KB Output is correct
14 Correct 531 ms 50256 KB Output is correct

Subtask #5
0 / 12.0

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