Submission #583823

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583823	2022-06-26T09:03:59 Z	MohamedFaresNebili	Toy Train (IOI17_train)	C++14	11 / 100	1162 ms	99744 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);
            for(auto u : adj[v]) {
                if(solve(v + 1, t - 1, A))
                    return 1;
           }
           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:73:22: warning: unused variable 'u' [-Wunused-variable]
   73 |             for(auto u : adj[v]) {
      |                      ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	42 ms	98220 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	353 ms	99628 KB	Output is correct
2	Correct	296 ms	99660 KB	Output is correct
3	Correct	269 ms	99552 KB	Output is correct
4	Correct	48 ms	99372 KB	Output is correct
5	Correct	232 ms	99380 KB	Output is correct
6	Correct	1162 ms	99744 KB	Output is correct
7	Correct	48 ms	99404 KB	Output is correct
8	Correct	535 ms	99332 KB	Output is correct
9	Correct	776 ms	99340 KB	Output is correct
10	Correct	207 ms	99236 KB	Output is correct
11	Correct	258 ms	99276 KB	Output is correct
12	Correct	49 ms	98764 KB	Output is correct
13	Correct	62 ms	99404 KB	Output is correct
14	Correct	57 ms	99416 KB	Output is correct
15	Correct	59 ms	99404 KB	Output is correct
16	Correct	52 ms	99304 KB	Output is correct
17	Correct	54 ms	99368 KB	Output is correct
18	Correct	47 ms	98920 KB	Output is correct