oj.uz

Submission #33248

# Submission time Handle Problem Language Result Execution time Memory
33248 2017-10-23T04:36:36 Z model_code Toy Train (IOI17_train) C++11
11 / 100
 96 ms 3340 KB 
#include "train.h"

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>

using namespace std;

const int MAXN = 5000+10;

const int B = 0;
const int A = 1;

bool del[MAXN];
int n;
int mark[MAXN], need[MAXN], par[MAXN];
vector<int> a, r, res;
vector<int> adj[MAXN], bak[MAXN];

bool dfs (int v) {
    mark[v] = 1;
    for (int i = 0; i < (int)adj[v].size(); i++) {
        int u = adj[v][i];
        if (del[u] || r[u])
            continue;
        if (mark[u] == 0) {
            par[u] = v;
            if (dfs(u))
                return true;
        } else if (mark[u] == 1) {
            int cur = v;
            while (true) {
                res[cur] = B;
                if (cur == u)
                    break;
                cur = par[cur];
            }
            return true;
        }
    }
    mark[v] = 2;
    return false;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
    ::a = a, ::r = r;
    for (int i = 0; i < (int)u.size(); i++) {
        adj[u[i]].push_back(v[i]);
        bak[v[i]].push_back(u[i]);
    }
    n = (int)a.size();
    res.resize(n, A);
    while (true) {
        memset(mark, 0, sizeof mark);
        bool flag = false;
        for (int i = 0; i < n && !flag; i++) if (r[i] == 0 && del[i] == false && mark[i] == 0)
            flag = dfs(i);
        if (flag == false)
            break;
        memset(need, 0, sizeof need);
        queue<int> q;
        for (int i = 0; i < n; i++) if (del[i] == false) {
            if (res[i] == B)
                q.push(i);
            else {
                if (a[i] == B)
                    need[i] = 1;
                else {
                    for (int j = 0; j < (int)adj[i].size(); j++) if (del[adj[i][j]] == false)
                        need[i]++;
                }
            }
        }
        while (!q.empty()) {
            int front = q.front(); q.pop();
            del[front] = true;
            for (int i = 0; i < (int)bak[front].size(); i++) {
                int temp = bak[front][i];
                --need[temp];
                if (need[temp] == 0 && res[temp] == A) {
                    res[temp] = B;
                    q.push(temp);
                }
            }
        }
    }
    return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 2864 KB 3rd lines differ - on the 26th 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 2320 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 23 ms 3340 KB Output is correct
2 Correct 56 ms 3204 KB Output is correct
3 Correct 96 ms 3204 KB Output is correct
4 Incorrect 19 ms 3204 KB 3rd lines differ - on the 8th 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 9 ms 3064 KB Output is correct
2 Correct 9 ms 3184 KB Output is correct
3 Correct 6 ms 3204 KB Output is correct
4 Correct 6 ms 3204 KB Output is correct
5 Correct 9 ms 3200 KB Output is correct
6 Correct 6 ms 3192 KB Output is correct
7 Correct 9 ms 3192 KB Output is correct
8 Correct 6 ms 3180 KB Output is correct
9 Correct 16 ms 3180 KB Output is correct
10 Correct 13 ms 3204 KB Output is correct
11 Correct 6 ms 3204 KB Output is correct
12 Correct 6 ms 3204 KB Output is correct
13 Correct 6 ms 3204 KB Output is correct
14 Correct 6 ms 3192 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 3204 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 59 ms 2864 KB 3rd lines differ - on the 26th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -