oj.uz

Submission #713509

# Submission time Handle Problem Language Result Execution time Memory
713509 2023-03-22T10:47:22 Z MohamedFaresNebili Toy Train (IOI17_train) C++14
11 / 100
 51 ms 99608 KB 
#include <bits/stdc++.h>

        using namespace std;

        int N, M, timer, tin[5001], low[5001];
        vector<int> adj[5001], G[5001], S;
        bool vis[5001], self[5001], Scc[5001], ST[5001];
        int DP[5001][5001];

        void dfs(int v) {
            tin[v] = low[v] = timer++;
            vis[v] = 1; S.push_back(v);
            for(auto u : G[v]) {
                if(tin[u] == -1) dfs(u);
                if(vis[u]) low[v] = min(low[v], low[u]);
            }
            if(tin[v] == low[v]) {
                vector<int> V;
                while(1) {
                    int U = S.back(); S.pop_back();
                    vis[U] = 0; V.push_back(U);
                    if(U == v) break;
                }
                if(V.size() == 1) return;
                for(auto u : V) {
                    Scc[u] = 1;
                }
            }
        }

        vector<int> who_wins(vector<int> A, vector<int> R,
                             vector<int> U, vector<int> V) {
            N = A.size(), M = U.size();
            for(int l = 0; l < N; l++)
                ST[l] = R[l];
            for(int l = 0; l < M; l++) {
                int X = U[l], Y = V[l];
                if(X == Y) {
                    self[X] = 1;
                    if(ST[X] == 0) Scc[X] = 1;
                    continue;
                }
                adj[Y].push_back(X);
                if(ST[X] == ST[Y] && ST[X] == 0)
                    G[X].push_back(Y);
            }
            memset(tin, -1, sizeof tin);
            memset(DP, -1, sizeof DP);
            for(int l = 0; l < N; l++) {
                if(tin[l] != -1) continue;
                dfs(l);
            }
            queue<pair<int, int>> q;
            vector<int> D(N, 1e9 + 7);
            for(int l = 0; l < N; l++) {
                if(Scc[l])
                    D[l] = 0, q.push({l, 0});
            }
            while(!q.empty()) {
                int X = q.front().first;
                int C = q.front().second;
                q.pop();
                for(auto Y : adj[X]) {
                    if(D[Y] > D[X] + 1) {
                        D[Y] = D[X] + 1;
                        q.push({Y, D[Y]});
                    }
                }
            }
            vector<int> res(N, 0);
            for(int l = 0; l < N; l++)
                res[l] = (D[l] == 1e9 + 7);
            return res;
        }

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:61:21: warning: unused variable 'C' [-Wunused-variable]
   61 |                 int C = q.front().second;
      |                     ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 98864 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 40 ms 98332 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 45 ms 99596 KB Output is correct
2 Correct 44 ms 99376 KB Output is correct
3 Correct 45 ms 99384 KB Output is correct
4 Incorrect 51 ms 99416 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 44 ms 98924 KB Output is correct
2 Correct 46 ms 99336 KB Output is correct
3 Correct 45 ms 99380 KB Output is correct
4 Correct 45 ms 99368 KB Output is correct
5 Correct 47 ms 99488 KB Output is correct
6 Correct 46 ms 99484 KB Output is correct
7 Correct 44 ms 99452 KB Output is correct
8 Correct 46 ms 99400 KB Output is correct
9 Correct 44 ms 99152 KB Output is correct
10 Correct 44 ms 99212 KB Output is correct
11 Correct 44 ms 99276 KB Output is correct
12 Correct 45 ms 99240 KB Output is correct
13 Correct 46 ms 99608 KB Output is correct
14 Correct 47 ms 99476 KB Output is correct

Subtask #5
0 / 12.0

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