Submission #583821

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583821	2022-06-26T09:01:43 Z	MohamedFaresNebili	Toy Train (IOI17_train)	C++14	11 / 100	1116 ms	99760 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;
                for(auto u : adj[v]) {
                    if(solve(v + 1, t - 1, A))
                        return 1;
                }
                return 0;
            }
            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:65:26: warning: unused variable 'u' [-Wunused-variable]
   65 |                 for(auto u : adj[v]) {
      |                          ^
train.cpp:75:9: warning: control reaches end of non-void function [-Wreturn-type]
   75 |         }
      |         ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	19 ms	1232 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	44 ms	98384 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	381 ms	99624 KB	Output is correct
2	Correct	279 ms	99576 KB	Output is correct
3	Correct	328 ms	99560 KB	Output is correct
4	Correct	48 ms	99400 KB	Output is correct
5	Correct	205 ms	99348 KB	Output is correct
6	Correct	1116 ms	99760 KB	Output is correct
7	Correct	47 ms	99404 KB	Output is correct
8	Correct	509 ms	99376 KB	Output is correct
9	Correct	800 ms	99332 KB	Output is correct
10	Correct	197 ms	99416 KB	Output is correct
11	Correct	261 ms	99304 KB	Output is correct
12	Correct	47 ms	98764 KB	Output is correct
13	Correct	65 ms	99376 KB	Output is correct
14	Correct	57 ms	99436 KB	Output is correct
15	Correct	57 ms	99332 KB	Output is correct
16	Correct	52 ms	99416 KB	Output is correct
17	Correct	56 ms	99312 KB	Output is correct
18	Correct	57 ms	98868 KB	Output is correct