oj.uz

Submission #1015328

# Submission time Handle Problem Language Result Execution time Memory
1015328 2024-07-06T08:45:39 Z hotboy2703 Toy Train (IOI17_train) C++17
28 / 100
 87 ms 1372 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 < sz(u);i ++){g[v[i]].push_back(u[i]);cnt[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);
                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 (!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)cout<<x<<' ';
//        cout<<endl;
        vector <ll> X;
        for (ll i = 0;i < n;i ++){
            if (res[i] == -1 && !in[i]){X.push_back(i);in[i] = 1;}
        }
        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;
//        for (auto u:X)cout<<u<<' ';
//        cout<<endl;
//        cout<<cnt[0]<<endl;
        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 u:R){
            res[u] = 0;
            in[u] = 0;
            for (auto v:g[u]){
                if (a[v])cnt[v]++;
            }
        }
    }
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 3 ms 1080 KB Output is correct
3 Correct 3 ms 988 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 828 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 2 ms 960 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 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 42 ms 1116 KB Output is correct
2 Correct 79 ms 1116 KB Output is correct
3 Correct 87 ms 1116 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Incorrect 5 ms 1372 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 4 ms 1116 KB Output is correct
2 Correct 4 ms 1112 KB Output is correct
3 Correct 4 ms 1236 KB Output is correct
4 Correct 4 ms 1372 KB Output is correct
5 Correct 4 ms 1372 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 4 ms 1372 KB Output is correct
8 Correct 4 ms 1264 KB Output is correct
9 Correct 4 ms 1372 KB Output is correct
10 Correct 4 ms 1372 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Correct 4 ms 1372 KB Output is correct
13 Correct 4 ms 1220 KB Output is correct
14 Correct 4 ms 1368 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1116 KB Output is correct
2 Correct 4 ms 1332 KB Output is correct
3 Correct 4 ms 1344 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 4 ms 1112 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 1 ms 600 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 3 ms 856 KB Output is correct
2 Correct 3 ms 1080 KB Output is correct
3 Correct 3 ms 988 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 828 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 2 ms 960 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 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 -