oj.uz

Submission #577622

# Submission time Handle Problem Language Result Execution time Memory
577622 2022-06-15T06:38:16 Z Theo830 Toy Train (IOI17_train) C++17
11 / 100
 1756 ms 1388 KB 
#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,adj2;
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());
	adj2.assign(n+5,vll());
	f(i,0,m){
        adj[u[i]].pb(v[i]);
        if(!r[u[i]] && !r[v[i]]){
            adj2[u[i]].pb(v[i]);
        }
	}
	f(i,0,n){
        if(r[i] == 0){
            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:adj2[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);
                }
            }
        }
        res[i] ^= 1;
	}
	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 249 ms 936 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 0 ms 212 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 279 ms 1388 KB Output is correct
2 Correct 231 ms 1364 KB Output is correct
3 Correct 145 ms 1336 KB Output is correct
4 Incorrect 1287 ms 1268 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 695 ms 1028 KB Output is correct
2 Correct 235 ms 1252 KB Output is correct
3 Correct 420 ms 1320 KB Output is correct
4 Correct 479 ms 1208 KB Output is correct
5 Correct 759 ms 1336 KB Output is correct
6 Correct 575 ms 1316 KB Output is correct
7 Correct 624 ms 1288 KB Output is correct
8 Correct 407 ms 1240 KB Output is correct
9 Correct 27 ms 980 KB Output is correct
10 Correct 824 ms 1168 KB Output is correct
11 Correct 848 ms 1168 KB Output is correct
12 Correct 861 ms 1168 KB Output is correct
13 Correct 887 ms 1364 KB Output is correct
14 Correct 530 ms 1284 KB Output is correct

Subtask #5
0 / 12.0

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