Submission #583817

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583817	2022-06-26T08:45:57 Z	MohamedFaresNebili	Toy Train (IOI17_train)	C++14	11 / 100	1131 ms	100048 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];
        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;
        }

        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];
            for(int l = 0; l < M; l++) {
                int u = U[l], v = V[l];
                if(u == v) {
                    Scc[u] = station[u];
                    continue;
                }
                adj[u].pb(v);
            }
            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:31:37: warning: variable 'valid' set but not used [-Wunused-but-set-variable]
   31 |                 vector<int> V; bool valid = 0;
      |                                     ^~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	41 ms	99368 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	98256 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	350 ms	99616 KB	Output is correct
2	Correct	291 ms	99780 KB	Output is correct
3	Correct	276 ms	99760 KB	Output is correct
4	Correct	57 ms	99644 KB	Output is correct
5	Correct	207 ms	99588 KB	Output is correct
6	Correct	1131 ms	100048 KB	Output is correct
7	Correct	49 ms	99560 KB	Output is correct
8	Correct	569 ms	99552 KB	Output is correct
9	Correct	879 ms	99516 KB	Output is correct
10	Correct	210 ms	99512 KB	Output is correct
11	Correct	267 ms	99488 KB	Output is correct
12	Correct	48 ms	99020 KB	Output is correct
13	Correct	57 ms	99532 KB	Output is correct
14	Correct	49 ms	99624 KB	Output is correct
15	Correct	65 ms	99568 KB	Output is correct
16	Correct	49 ms	99532 KB	Output is correct
17	Correct	51 ms	99564 KB	Output is correct
18	Correct	44 ms	99012 KB	Output is correct