Submission #583825

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583825	2022-06-26T09:06:50 Z	MohamedFaresNebili	Toy Train (IOI17_train)	C++14	11 / 100	1080 ms	99876 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]) {
                for(auto u : adj[v]) 
                  return solve(v + 1, t - 1, A);
              	return 0;
            }
            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;
      |                                     ^~~~~
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:72:26: warning: unused variable 'u' [-Wunused-variable]
   72 |                 for(auto u : adj[v])
      |                          ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	1464 KB	Output is correct
2	Incorrect	76 ms	1548 KB	3rd lines differ - on the 4997th token, expected: '1', found: '0'
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	41 ms	98252 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	424 ms	99624 KB	Output is correct
2	Correct	297 ms	99580 KB	Output is correct
3	Correct	278 ms	99564 KB	Output is correct
4	Correct	48 ms	99452 KB	Output is correct
5	Correct	203 ms	99372 KB	Output is correct
6	Correct	1080 ms	99876 KB	Output is correct
7	Correct	46 ms	99276 KB	Output is correct
8	Correct	503 ms	99380 KB	Output is correct
9	Correct	770 ms	99332 KB	Output is correct
10	Correct	205 ms	99276 KB	Output is correct
11	Correct	275 ms	99300 KB	Output is correct
12	Correct	50 ms	98772 KB	Output is correct
13	Correct	67 ms	99392 KB	Output is correct
14	Correct	49 ms	99396 KB	Output is correct
15	Correct	56 ms	99424 KB	Output is correct
16	Correct	47 ms	99380 KB	Output is correct
17	Correct	50 ms	99408 KB	Output is correct
18	Correct	43 ms	98892 KB	Output is correct