oj.uz

Submission #583827

# Submission time Handle Problem Language Result Execution time Memory
583827 2022-06-26T09:12:07 Z MohamedFaresNebili Toy Train (IOI17_train) C++14
16 / 100
 1119 ms 99808 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

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

        void dfs(int v) {
            tin[v] = low[v] = timer++;
            S.push_back(v); vis[v] = 1;
            for(auto u : adj[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; bool valid = 0;
                while(1) {
                    int U = S.back(); S.pop_back();
                    V.push_back(U); vis[U] = 0;
                    if(station[U]) valid = 1;
                    if(U == v) break;
                }
                if(V.size() == 1) return;
                for(auto u : V)
                    Scc[u] = station[u];
            }
        }
        int solve(int v, int t) {
            if(Scc[v]) return 1;
            if(DP[v][t] != -1) return DP[v][t];
            if(station[v]) t = N;
            if(DP[v][t] != -1) return DP[v][t];
            if(t) {
                for(auto u : adj[v]) {
                    if(solve(u, t - 1))
                        return DP[v][t] = 1;
                }
            }
            if(station[v] && adj[v].size() == 0)
                return DP[v][t] = 1;
            return DP[v][t] = 0;
        }
        int solve(int v, int t, vector<int> A) {
            if(v >= N) return 0;
            if(station[v]) t = N;

            if(A[v] == 1) {
                if(self[v] && station[v])
                    return 1;
                if(self[v]) {
                    if(adj[v].size())
                        return solve(v + 1, t - 1, A);
                    return 0;
                }
                return solve(v + 1, t - 1, A);
            }

            if(self[v] && station[v]) {
                if(adj[v].size())
                    return solve(v + 1, t - 1, A);
                return 1;
            }
            if(self[v]) return 0;
            return solve(v + 1, t - 1, A);
        }
        vector<int> subtask1(vector<int> A) {
            vector<int> res(N, 0);
            for(int l = 0; l < N; l++) {
                res[l] = solve(l, N, A);
            }
            return res;
        }

        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++)
                station[l] = R[l];
            bool ok = 1;
            for(int l = 0; l < M; l++) {
                int u = U[l], v = V[l];
                if(u == v) {
                    Scc[u] = station[u];
                    self[u] = 1; continue;
                }
                adj[u].pb(v); ok &= (v == u + 1);
            }
            if(ok) return subtask1(A);
            memset(tin, -1, sizeof tin);
            memset(DP, -1, sizeof DP);
            for(int l = 0; l < N; l++) {
                if(tin[l] != -1) continue;
                dfs(l);
            }
            vector<int> res(N);
            for(int l = 0; l < N; l++) {
                res[l] = solve(l, N);
            }
            return res;
        }

Compilation message

train.cpp: In function 'void dfs(int)':
train.cpp:32:37: warning: variable 'valid' set but not used [-Wunused-but-set-variable]
   32 |                 vector<int> V; bool valid = 0;
      |                                     ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1444 KB Output is correct
2 Correct 77 ms 1548 KB Output is correct
3 Correct 96 ms 1572 KB Output is correct
4 Correct 92 ms 1696 KB Output is correct
5 Correct 88 ms 1660 KB Output is correct
6 Correct 57 ms 1516 KB Output is correct
7 Correct 65 ms 1432 KB Output is correct
8 Correct 54 ms 1408 KB Output is correct
9 Correct 24 ms 1272 KB Output is correct
10 Correct 9 ms 968 KB Output is correct
11 Correct 6 ms 724 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 98236 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 99628 KB Output is correct
2 Correct 303 ms 99572 KB Output is correct
3 Correct 275 ms 99556 KB Output is correct
4 Correct 44 ms 99408 KB Output is correct
5 Correct 205 ms 99396 KB Output is correct
6 Correct 1119 ms 99808 KB Output is correct
7 Correct 51 ms 99276 KB Output is correct
8 Correct 508 ms 99276 KB Output is correct
9 Correct 784 ms 99328 KB Output is correct
10 Correct 197 ms 99320 KB Output is correct
11 Correct 268 ms 99300 KB Output is correct
12 Correct 47 ms 98768 KB Output is correct
13 Correct 66 ms 99320 KB Output is correct
14 Correct 53 ms 99420 KB Output is correct
15 Correct 61 ms 99340 KB Output is correct
16 Correct 53 ms 99404 KB Output is correct
17 Correct 63 ms 99408 KB Output is correct
18 Correct 55 ms 98852 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 99156 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 99340 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1444 KB Output is correct
2 Correct 77 ms 1548 KB Output is correct
3 Correct 96 ms 1572 KB Output is correct
4 Correct 92 ms 1696 KB Output is correct
5 Correct 88 ms 1660 KB Output is correct
6 Correct 57 ms 1516 KB Output is correct
7 Correct 65 ms 1432 KB Output is correct
8 Correct 54 ms 1408 KB Output is correct
9 Correct 24 ms 1272 KB Output is correct
10 Correct 9 ms 968 KB Output is correct
11 Correct 6 ms 724 KB Output is correct
12 Incorrect 38 ms 98236 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -