oj.uz

Submission #1015359

# Submission time Handle Problem Language Result Execution time Memory
1015359 2024-07-06T09:14:08 Z hotboy2703 Toy Train (IOI17_train) C++17
28 / 100
 82 ms 1276 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];
ll sus[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 < sz(u);i ++){g[v[i]].push_back(u[i]);cnt[u[i]]++;sus[u[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);
        }
        if (sz(R)==0){
            for (ll i = 0;i < n;i ++){
                if (res[i] == -1)res[i] = 0;
            }
            break;
        }

        for (auto x:R)in[x] = 1;
        for (ll i = 0;i < n;i ++)if (res[i] != -1)in[i] = 1;
        ll ptr = 0;
        while (ptr < sz(R)){
            ll u = R[ptr];
            ptr++;
            for (auto v:g[u]){
                if (!a[v])cnt[v]--;
                if (in[v])continue;
                if (a[v]){
                    in[v] = 1;
                    R.push_back(v);
                }
                else {
                    if (cnt[v]==0){in[v] = 1;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 (ll i = 0;i < n;i ++){
            in[i] = 0;
            cnt[i] = sus[i];
        }

        R=X;
        for (auto x:R)in[x] = 1;
        for (ll i = 0;i < n;i ++)if (res[i] != -1)in[i] = 1;
        ptr = 0;
        while (ptr < sz(R)){
            ll u = R[ptr];
            ptr++;
            for (auto v:g[u]){
                if (a[v])cnt[v]--;
                if (in[v])continue;
                if (!a[v]){
                    in[v] = 1;
                    R.push_back(v);
                }
                else {
                    if (cnt[v]==0){in[v] = 1;R.push_back(v);}
                }
            }
        }

        for (auto x:R)res[x] = 0;

        for (ll i = 0;i < n;i ++){
            in[i] = 0;
            cnt[i] = sus[i];
        }

    }
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 3 ms 856 KB Output is correct
3 Correct 3 ms 912 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 908 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 3 ms 908 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 896 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1116 KB Output is correct
2 Correct 64 ms 1276 KB Output is correct
3 Correct 82 ms 1116 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Incorrect 4 ms 1268 KB 3rd lines differ - on the 11th token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 4 ms 1116 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 5 ms 1116 KB Output is correct
8 Correct 4 ms 1116 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 4 ms 1116 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct
14 Correct 4 ms 1116 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1112 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 4 ms 1116 KB Output is correct
4 Correct 3 ms 992 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 860 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 3 ms 856 KB Output is correct
3 Correct 3 ms 912 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 908 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 3 ms 908 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 896 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
20 Halted 0 ms 0 KB -