oj.uz

Submission #1015296

# Submission time Handle Problem Language Result Execution time Memory
1015296 2024-07-06T08:29:36 Z hotboy2703 Toy Train (IOI17_train) C++17
0 / 100
 312 ms 262144 KB 
#include "train.h"

#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 5e3+10;
vector <ll> g[MAXN];
ll cnt[MAXN];
bool in[MAXN];
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    ll n =  sz(a);
    for (ll i = 0;i < n;i ++){g[u[i]].push_back(v[i]);cnt[v[i]]++;}
    vector <ll> res(n,-1);
    while (1){
        vector <ll> R;
        for (ll i = 0;i < n;i ++){
            if (res[i] == -1 && r[i]){
                R.push_back(i);
                in[i] = 1;
            }
        }
        if (sz(R)==0){
            for (ll i = 0;i < n;i ++){
                res[i] = 0;
                break;
            }
        }
        ll ptr = 0;
        while (ptr < sz(R)){
            ll u = R[ptr];
            ptr++;
            for (auto v:g[u]){
                if (in[v])continue;
                if (a[v]){
                    R.push_back(v);
                }
                else {
                    cnt[v]--;
                    if (cnt[v]==0)R.push_back(v);
                }
            }
        }
        vector <ll> X;
        for (ll i = 0;i < n;i ++){
            if (res[i] == -1 && !in[i])X.push_back(i);
        }
        if (sz(X)==0){
            for (auto u:R){
                res[u] = 1;
            }
            break;
        }
        for (auto u:R){
            in[u] = 0;
            for (auto v:g[u]){
                if (!a[v])cnt[v]++;
            }
        }
        R=X;
        ptr = 0;
        while (ptr < sz(R)){
            ll u = R[ptr];
            ptr++;
            for (auto v:g[u]){
                if (in[v])continue;
                if (!a[v]){
                    R.push_back(v);
                }
                else {
                    cnt[v]--;
                    if (cnt[v]==0)R.push_back(v);
                }
            }
        }
        for (auto u:R){
            res[u] = 0;
            in[u] = 0;
            for (auto v:g[u]){
                if (a[v])cnt[v]++;
            }
        }
    }
	return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 276 ms 262144 KB Execution killed with signal 9
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 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 312 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 257 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1372 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 Runtime error 276 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -