Submission #583824

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583824	2022-06-26T09:05:20 Z	MohamedFaresNebili	Toy Train (IOI17_train)	C++14	11 / 100	1186 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;
                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;
          	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]) {
      |                          ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	1452 KB	Output is correct
2	Incorrect	81 ms	1616 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	45 ms	98212 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	372 ms	99660 KB	Output is correct
2	Correct	293 ms	99580 KB	Output is correct
3	Correct	272 ms	99668 KB	Output is correct
4	Correct	46 ms	99408 KB	Output is correct
5	Correct	206 ms	99308 KB	Output is correct
6	Correct	1186 ms	99752 KB	Output is correct
7	Correct	49 ms	99364 KB	Output is correct
8	Correct	553 ms	99348 KB	Output is correct
9	Correct	869 ms	99332 KB	Output is correct
10	Correct	214 ms	99324 KB	Output is correct
11	Correct	295 ms	99312 KB	Output is correct
12	Correct	44 ms	98764 KB	Output is correct
13	Correct	58 ms	99420 KB	Output is correct
14	Correct	52 ms	99316 KB	Output is correct
15	Correct	62 ms	99372 KB	Output is correct
16	Correct	51 ms	99408 KB	Output is correct
17	Correct	61 ms	99392 KB	Output is correct
18	Correct	50 ms	98932 KB	Output is correct