oj.uz

답안 #713509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713509 2023-03-22T10:47:22 Z MohamedFaresNebili 장난감 기차 (IOI17_train) C++14
11 / 100
 51 ms 99608 KB 
#include <bits/stdc++.h>

        using namespace std;

        int N, M, timer, tin[5001], low[5001];
        vector<int> adj[5001], G[5001], S;
        bool vis[5001], self[5001], Scc[5001], ST[5001];
        int DP[5001][5001];

        void dfs(int v) {
            tin[v] = low[v] = timer++;
            vis[v] = 1; S.push_back(v);
            for(auto u : G[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;
                while(1) {
                    int U = S.back(); S.pop_back();
                    vis[U] = 0; V.push_back(U);
                    if(U == v) break;
                }
                if(V.size() == 1) return;
                for(auto u : V) {
                    Scc[u] = 1;
                }
            }
        }

        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++)
                ST[l] = R[l];
            for(int l = 0; l < M; l++) {
                int X = U[l], Y = V[l];
                if(X == Y) {
                    self[X] = 1;
                    if(ST[X] == 0) Scc[X] = 1;
                    continue;
                }
                adj[Y].push_back(X);
                if(ST[X] == ST[Y] && ST[X] == 0)
                    G[X].push_back(Y);
            }
            memset(tin, -1, sizeof tin);
            memset(DP, -1, sizeof DP);
            for(int l = 0; l < N; l++) {
                if(tin[l] != -1) continue;
                dfs(l);
            }
            queue<pair<int, int>> q;
            vector<int> D(N, 1e9 + 7);
            for(int l = 0; l < N; l++) {
                if(Scc[l])
                    D[l] = 0, q.push({l, 0});
            }
            while(!q.empty()) {
                int X = q.front().first;
                int C = q.front().second;
                q.pop();
                for(auto Y : adj[X]) {
                    if(D[Y] > D[X] + 1) {
                        D[Y] = D[X] + 1;
                        q.push({Y, D[Y]});
                    }
                }
            }
            vector<int> res(N, 0);
            for(int l = 0; l < N; l++)
                res[l] = (D[l] == 1e9 + 7);
            return res;
        }

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:61:21: warning: unused variable 'C' [-Wunused-variable]
   61 |                 int C = q.front().second;
      |                     ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 98864 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 98332 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 99596 KB Output is correct
2 Correct 44 ms 99376 KB Output is correct
3 Correct 45 ms 99384 KB Output is correct
4 Incorrect 51 ms 99416 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98924 KB Output is correct
2 Correct 46 ms 99336 KB Output is correct
3 Correct 45 ms 99380 KB Output is correct
4 Correct 45 ms 99368 KB Output is correct
5 Correct 47 ms 99488 KB Output is correct
6 Correct 46 ms 99484 KB Output is correct
7 Correct 44 ms 99452 KB Output is correct
8 Correct 46 ms 99400 KB Output is correct
9 Correct 44 ms 99152 KB Output is correct
10 Correct 44 ms 99212 KB Output is correct
11 Correct 44 ms 99276 KB Output is correct
12 Correct 45 ms 99240 KB Output is correct
13 Correct 46 ms 99608 KB Output is correct
14 Correct 47 ms 99476 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 99516 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 98864 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -