Submission #970372

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
970372	2024-04-26T12:45:31 Z	GrindMachine	Toy Train (IOI17_train)	C++17	11 / 100	862 ms	50568 KB

train

#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> in_cyc(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]){
			if(v == r){
				in_cyc[r] = 1;
			}
		}
		else{
			dfs1(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);
	rep(i,n){
		fill(all(vis),0);
		dfs1(i,i);
	}

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

	return ans;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	199 ms	49872 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	2652 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	230 ms	50136 KB	Output is correct
2	Correct	246 ms	50156 KB	Output is correct
3	Correct	246 ms	50256 KB	Output is correct
4	Correct	832 ms	50308 KB	Output is correct
5	Correct	640 ms	50228 KB	Output is correct
6	Correct	496 ms	50092 KB	Output is correct
7	Correct	493 ms	50264 KB	Output is correct
8	Correct	282 ms	50020 KB	Output is correct
9	Correct	267 ms	49968 KB	Output is correct
10	Correct	352 ms	49988 KB	Output is correct
11	Correct	372 ms	50000 KB	Output is correct
12	Correct	69 ms	50036 KB	Output is correct
13	Correct	846 ms	50260 KB	Output is correct
14	Correct	838 ms	50536 KB	Output is correct
15	Correct	826 ms	50516 KB	Output is correct
16	Correct	862 ms	50568 KB	Output is correct
17	Correct	827 ms	50304 KB	Output is correct
18	Correct	357 ms	50036 KB	Output is correct