oj.uz

Submission #612473

# Submission time Handle Problem Language Result Execution time Memory
612473 2022-07-29T15:38:58 Z MohamedAliSaidane Toy Train (IOI17_train) C++14
11 / 100
 61 ms 99828 KB 
#include <bits/stdc++.h>
//#include "train.h"
    using namespace std;

    typedef long long ll;
    typedef double ld;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpi;
    typedef vector<pll> vpl;

    #define pb push_back
    #define popb pop_back
    #define all(x) (x).begin(),(x).end()

    #define ff first
    #define ss second

    const int nax = 5004;
    const int MOD = 1e9 + 7;
    int C[nax];
    vi adj[nax];
    vi rev_adj[nax];
    int A[nax];
    int n, m;
    int dp[nax][nax];
    int vis[nax], self[nax], ok[nax], del[nax];
    vi order, comp;
    void dfs(int x)
    {
        vis[x] = 1;
        for(auto e: adj[x])
        {
            if(!del[e] && !vis[e])
                dfs(e);
        }
        order.pb(x);
    }
    void dfs1(int x)
    {
        vis[x] = 1;
        for(auto e: rev_adj[x])
            if(!del[e] && !vis[e])
                dfs1(e);
        comp.pb(x);
    }
    vi who_wins(vi a, vi r, vi u, vi v)
    {
        memset(dp, -1,sizeof(dp));
        n = a.size();
        m = u.size();
        for(int i = 0 ; i < n; i++)
        {
            A[i] = a[i];
            C[i] = r[i];
            del[i] = C[i];
        }
        for(int i=  0; i < m; i++)
        {
            adj[u[i]].pb(v[i]);
            rev_adj[v[i]].pb(u[i]);
            if(u[i] == v[i])
                self[u[i]] = 1;
        }
        for(int i = 0 ; i <  n;i ++)
            if(!del[i] && !vis[i])
                dfs(i);
        reverse(all(order));
        memset(vis, false,sizeof(vis));
        for(auto e: order)
        {
            if(del[e] || vis[e])
                continue;
            comp.clear();
            dfs1(e);
            if(comp.size() > 1)
            {
                for(auto e: comp)
                    ok[e] = 1;
            }
            else if(self[comp[0]])
                ok[comp[0]] = 1;
        }
        queue<pii> q;
        int sp[n + 1];
        for(int i = 0; i < n; i++)
        {
            if(ok[i] )
            {
                sp[i] = 0;
                q.push({i, 0});
            }
            else
                sp[i] = MOD;
        }
        while(!q.empty())
        {
            int node = q.front().ff;
            int dis = q.front().ss;
            q.pop();
            for(auto e: rev_adj[node])
            {
                if(sp[e] > dis + 1)
                {
                    sp[e] = dis + 1;
                    q.push({e, dis + 1});
                }
            }
        }
        vi ans;
        for(int i=  0 ; i < n; i ++ )
        {
            if(sp[i] != MOD)
                ans.pb(0);
            else
                ans.pb(1);
        }
        return ans;

    }

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 99244 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 38 ms 98508 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 50 ms 99688 KB Output is correct
2 Correct 57 ms 99720 KB Output is correct
3 Correct 47 ms 99660 KB Output is correct
4 Incorrect 46 ms 99768 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 46 ms 99272 KB Output is correct
2 Correct 46 ms 99608 KB Output is correct
3 Correct 57 ms 99648 KB Output is correct
4 Correct 51 ms 99664 KB Output is correct
5 Correct 48 ms 99712 KB Output is correct
6 Correct 46 ms 99708 KB Output is correct
7 Correct 45 ms 99660 KB Output is correct
8 Correct 48 ms 99608 KB Output is correct
9 Correct 45 ms 99516 KB Output is correct
10 Correct 45 ms 99660 KB Output is correct
11 Correct 60 ms 99624 KB Output is correct
12 Correct 59 ms 99604 KB Output is correct
13 Correct 61 ms 99828 KB Output is correct
14 Correct 44 ms 99660 KB Output is correct

Subtask #5
0 / 12.0

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