Submission #577611

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
577611	2022-06-15T06:33:58 Z	Theo830	Toy Train (IOI17_train)	C++17	11 / 100	1269 ms	1052 KB

train

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define ull unsigned int
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "train.h"
bool ok[5005];
vector<vll>adj;
vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	vector<int> res(a.size());
	ll n = a.size();
	ll m = u.size();
	adj.assign(n+5,vll());
	f(i,0,m){
        adj[u[i]].pb(v[i]);
	}
	f(i,0,n){
        if(r[i] == 1){
            bool v[n+5] = {0};
            queue<ll>q;
            v[i] = 1;
            q.push(i);
            while(!q.empty()){
                ll f = q.front();
                q.pop();
                for(auto x:adj[f]){
                    if(!v[x]){
                        v[x] = 1;
                        q.push(x);
                    }
                    else if(x == i){
                        ok[i] = 1;
                        break;
                    }
                }
            }
        }
	}
	f(i,0,n){
	    res[i] = ok[i];
        bool v[n+5] = {0};
        queue<ll>q;
        v[i] = 1;
        q.push(i);
        while(!q.empty()){
            ll f = q.front();
            q.pop();
            for(auto x:adj[f]){
                if(!v[x]){
                    v[x] = 1;
                    res[i] |= ok[x];
                    q.push(x);
                }
            }
        }
	}
	return res;
}
/*
int main(){
	int n, m;
	assert(2 == scanf("%d %d", &n, &m));

	vector<int> a(n), r(n), u(m), v(m);

	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &a[i]));

	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));

	for(int i = 0; i < m; i++)
		assert(2 == scanf("%d %d", &u[i], &v[i]));

	vector<int> res = who_wins(a, r, u, v);

	for(int i = 0; i < (int)res.size(); i++)
		printf(i ? " %d" : "%d", res[i]);
	printf("\n");

	return 0;
}
*/

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	294 ms	764 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	0 ms	212 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	185 ms	1052 KB	Output is correct
2	Correct	184 ms	1044 KB	Output is correct
3	Correct	192 ms	1036 KB	Output is correct
4	Correct	1008 ms	1036 KB	Output is correct
5	Correct	636 ms	1036 KB	Output is correct
6	Correct	482 ms	1032 KB	Output is correct
7	Correct	655 ms	980 KB	Output is correct
8	Correct	295 ms	1020 KB	Output is correct
9	Correct	266 ms	1004 KB	Output is correct
10	Correct	339 ms	984 KB	Output is correct
11	Correct	283 ms	1000 KB	Output is correct
12	Correct	23 ms	852 KB	Output is correct
13	Correct	843 ms	1040 KB	Output is correct
14	Correct	790 ms	1040 KB	Output is correct
15	Correct	779 ms	1044 KB	Output is correct
16	Correct	781 ms	1044 KB	Output is correct
17	Correct	825 ms	1036 KB	Output is correct
18	Correct	335 ms	824 KB	Output is correct