oj.uz

Submission #826259

# Submission time Handle Problem Language Result Execution time Memory
826259 2023-08-15T11:38:07 Z vnm06 Toy Train (IOI17_train) C++14
11 / 100
 249 ms 1620 KB 
#include<bits/stdc++.h>
#include "train.h"

using namespace std;

int n, m;
bool isC[5005], used[5005];
bool badv[5005];
vector<int> gr[5005], rev_gr[5005];

void dfs(int v)
{
    int brs=gr[v].size();
    for(int i=0; i<brs; i++)
    {
        int nv=gr[v][i];
        if(used[nv]) continue;
        used[nv]=1;
        dfs(nv);
    }
}

vector<int> ans;

void dfs2(int v)
{
    ans[v-1]=1;
    int brs=rev_gr[v].size();
    for(int i=0; i<brs; i++)
    {
        int nv=rev_gr[v][i];
        if(ans[nv-1]) continue;
        dfs2(nv);
    }
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v)
{
    n=a.size();
    ans.resize(n);
    for(int i=0; i<n; i++) ans[i]=0;
    m=u.size();
    for(int i=0; i<n; i++)
    {
        if(r[i]) {isC[i+1]=1; badv[i+1]=1;}
    }
    for(int i=0; i<m; i++)
    {
        gr[u[i]+1].push_back(v[i]+1);
        rev_gr[v[i]+1].push_back(u[i]+1);
    }
    for(int t=1; t<=n; t++)
    {
    for(int i=1; i<=n; i++)
    {
        if(!badv[i])
        {
            bool fl0=0;
            int brs=gr[i].size();
            for(int j=0; j<brs; j++) if(!badv[gr[i][j]]) fl0=1;
            if(!fl0) badv[i]=1;
        }
    }
    }
    for(int k=1; k<=n; k++)
    {
        if(!badv[k]) dfs2(k);
    }
    for(int k=0; k<n; k++) ans[k]=1-ans[k];
    return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 980 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 1 ms 468 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 125 ms 1416 KB Output is correct
2 Correct 127 ms 1404 KB Output is correct
3 Correct 116 ms 1392 KB Output is correct
4 Incorrect 177 ms 1372 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 13 ms 1236 KB Output is correct
2 Correct 48 ms 1456 KB Output is correct
3 Correct 214 ms 1492 KB Output is correct
4 Correct 91 ms 1492 KB Output is correct
5 Correct 110 ms 1568 KB Output is correct
6 Correct 67 ms 1548 KB Output is correct
7 Correct 77 ms 1544 KB Output is correct
8 Correct 191 ms 1508 KB Output is correct
9 Correct 26 ms 1468 KB Output is correct
10 Correct 15 ms 1596 KB Output is correct
11 Correct 13 ms 1488 KB Output is correct
12 Correct 14 ms 1620 KB Output is correct
13 Correct 171 ms 1568 KB Output is correct
14 Correct 89 ms 1480 KB Output is correct

Subtask #5
0 / 12.0

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