Submission #713532

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713532	2023-03-22T11:52:19 Z	MohamedFaresNebili	Toy Train (IOI17_train)	C++14	11 / 100	1286 ms	99420 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] = valid;
            }
        }
        int solve(int v, int t) {
            if(Scc[v]) return 1;
            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 'int solve(int, int, std::vector<int>)':
train.cpp:63:26: warning: unused variable 'u' [-Wunused-variable]
   63 |                 for(auto u : adj[v]) {
      |                          ^
train.cpp:70:26: warning: unused variable 'u' [-Wunused-variable]
   70 |                 for(auto u : adj[v])
      |                          ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	1420 KB	Output is correct
2	Incorrect	77 ms	1524 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	51 ms	98276 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	357 ms	99360 KB	Output is correct
2	Correct	241 ms	99236 KB	Output is correct
3	Correct	286 ms	99276 KB	Output is correct
4	Correct	45 ms	99364 KB	Output is correct
5	Correct	266 ms	99220 KB	Output is correct
6	Correct	1286 ms	99284 KB	Output is correct
7	Correct	44 ms	98956 KB	Output is correct
8	Correct	611 ms	99196 KB	Output is correct
9	Correct	910 ms	99252 KB	Output is correct
10	Correct	240 ms	99260 KB	Output is correct
11	Correct	310 ms	99128 KB	Output is correct
12	Correct	43 ms	98780 KB	Output is correct
13	Correct	43 ms	99404 KB	Output is correct
14	Correct	45 ms	99388 KB	Output is correct
15	Correct	48 ms	99420 KB	Output is correct
16	Correct	45 ms	99356 KB	Output is correct
17	Correct	43 ms	99404 KB	Output is correct
18	Correct	434 ms	99000 KB	Output is correct