Submission #583819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583819	2022-06-26T09:00:17 Z	MohamedFaresNebili	Toy Train (IOI17_train)	C++14	11 / 100	1096 ms	99752 KB

train

#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(station[v] && self[v])
                    return 1;
                return solve(v + 1, t - 1, A);
            }
            if(station[v])
                return solve(v + 1, t - 1, A);
            if(self[v]) return 0;

        }
        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;
      |                                     ^~~~~
train.cpp: In function 'int solve(int, int, std::vector<int>)':
train.cpp:71:9: warning: control reaches end of non-void function [-Wreturn-type]
   71 |         }
      |         ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	20 ms	1204 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	47 ms	98312 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	391 ms	99752 KB	Output is correct
2	Correct	285 ms	99576 KB	Output is correct
3	Correct	287 ms	99556 KB	Output is correct
4	Correct	44 ms	99348 KB	Output is correct
5	Correct	201 ms	99492 KB	Output is correct
6	Correct	1096 ms	99748 KB	Output is correct
7	Correct	50 ms	99284 KB	Output is correct
8	Correct	506 ms	99352 KB	Output is correct
9	Correct	774 ms	99332 KB	Output is correct
10	Correct	207 ms	99276 KB	Output is correct
11	Correct	255 ms	99308 KB	Output is correct
12	Correct	48 ms	98852 KB	Output is correct
13	Correct	66 ms	99320 KB	Output is correct
14	Correct	52 ms	99408 KB	Output is correct
15	Correct	67 ms	99420 KB	Output is correct
16	Correct	55 ms	99408 KB	Output is correct
17	Correct	52 ms	99320 KB	Output is correct
18	Correct	46 ms	98896 KB	Output is correct