oj.uz

Submission #1037580

# Submission time Handle Problem Language Result Execution time Memory
1037580 2024-07-29T04:58:15 Z sleepntsheep Toy Train (IOI17_train) C++17
27 / 100
 849 ms 99412 KB 
#include "train.h"
#include<queue>
#include <algorithm>

using namespace std;

struct dsu {
    vector<int> p;
    dsu(int n) : p(n, -1) {}
    int find(int i) { return p[i] < 0 ? i : (p[i] = find(p[i])); }
    int unite(int i, int j) { if (find(i) == find(j)) return 0; p[find(i)] = find(j); return 1; }
};

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {

    int n = a.size();
    int m = u.size();

    int is_subtask_1 = 1;
    int is_subtask_3 = *min_element(a.begin(), a.end()) == 1;
    int is_subtask_4 = *max_element(a.begin(), a.end()) == 0;
    for (int i = 0; i < m; ++i) is_subtask_1 &= (u[i] == v[i]) + (u[i] == v[i] - 1);

    std::vector<int> res(n);

    if (is_subtask_1) {
        std::vector<int> loop(n), go(n);
        for (int i = 0; i < m; ++i)
            if (u[i] == v[i]) loop[u[i]] = 1;
            else go[u[i]] = 1;
        if (r[n-1]) res[n-1] = 1;
        for (int i = n - 2; i >= 0; --i)
            if (a[i]) {
                if (loop[i]) {
                    if (r[i]) res[i] = 1;
                    else {
                        if (go[i]) res[i] = res[i + 1];
                        else res[i] = 0;
                    }
                } else res[i] = res[i + 1];
            } else {
                if (loop[i]) {
                    if (r[i]) {
                        if (go[i]) res[i] = res[i + 1];
                        else res[i] = 1;
                    }
                    else res[i] = 0;
                } else res[i] = res[i + 1];
            }
    } else if (is_subtask_3) {
        vector<vector<int> > g(n);
        vector<int>loop(n);
        for(int i=0;i<m;++i){g[u[i]].push_back(v[i]); if(u[i]==v[i])loop[u[i]]=1; }

        vector<vector<int> > dp(n, vector<int>(n, 1e9));

        for(int i=0;i<n;++i){
            queue<int>q;
            dp[i][i]=0;
            q.push(i);while(q.size()){ auto u=q.front();q.pop();for(auto v:g[u])if(dp[i][v]==1e9)q.push(v),dp[i][v]=dp[i][u]+1; }
        }

        vector<int>good;
        for(int i=0;i<n;++i){
            if(r[i]==0)continue;
            if(loop[i])good.push_back(i);
            else{
                for(int j=0;j<n;++j){
                    if(j!=i&&dp[j][i]<1e9&&dp[i][j]<1e9){
                        good.push_back(i);
                        break;
                    }
                }
            }
        }


        for(int i=0;i<n;++i){
            for(auto x:good)if(dp[i][x]<1e9){res[i]=1;break;}
        }
        return res;
    } else if (is_subtask_4) {
        vector<vector<int> > g(n);
        vector<int>loop(n);
        for(int i=0;i<m;++i){g[u[i]].push_back(v[i]); if(u[i]==v[i])loop[u[i]]=1; }

        vector<vector<int> > dp(n, vector<int>(n, 1e9));

        for(int i=0;i<n;++i){
            deque<int>q;
            dp[i][i]=0;
            q.push_front(i);while(q.size()){ auto u=q.front();q.pop_front();
                for(auto v:g[u]){
                    int weght=r[v];
                    if(dp[i][v]>dp[i][u]+weght){
                        if(weght)q.push_back(v);
                        else q.push_front(v);
                        dp[i][v]=dp[i][u]+weght;
                    }
                }
            }
        }

        vector<int>good;
        for(int i=0;i<n;++i){
            if(r[i]==1)continue;
            if(loop[i])good.push_back(i);
            else{
                for(int j=0;j<n;++j){
                    if(j!=i&&dp[j][i]==0&&dp[i][j]==0){
                        good.push_back(i);
                        break;
                    }
                }
            }
        }

        fill(res.begin(),res.end(),1);

        for(int i=0;i<n;++i){
            for(auto x:good)if(dp[i][x]<1e9){res[i]=0;break;}
        }
        return res;
    }
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 99120 KB Output is correct
2 Correct 228 ms 99160 KB Output is correct
3 Correct 230 ms 99152 KB Output is correct
4 Correct 720 ms 99148 KB Output is correct
5 Correct 584 ms 99228 KB Output is correct
6 Correct 441 ms 99152 KB Output is correct
7 Correct 420 ms 99148 KB Output is correct
8 Correct 307 ms 99156 KB Output is correct
9 Correct 280 ms 99192 KB Output is correct
10 Correct 354 ms 99156 KB Output is correct
11 Correct 312 ms 99164 KB Output is correct
12 Correct 76 ms 98924 KB Output is correct
13 Correct 710 ms 99224 KB Output is correct
14 Correct 740 ms 99408 KB Output is correct
15 Correct 695 ms 99152 KB Output is correct
16 Correct 735 ms 99160 KB Output is correct
17 Correct 754 ms 99224 KB Output is correct
18 Correct 315 ms 98896 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 98900 KB Output is correct
2 Correct 319 ms 99040 KB Output is correct
3 Correct 427 ms 99224 KB Output is correct
4 Correct 514 ms 99408 KB Output is correct
5 Correct 476 ms 99212 KB Output is correct
6 Correct 438 ms 99408 KB Output is correct
7 Correct 442 ms 99192 KB Output is correct
8 Correct 443 ms 99156 KB Output is correct
9 Correct 78 ms 99060 KB Output is correct
10 Correct 849 ms 99228 KB Output is correct
11 Correct 804 ms 99412 KB Output is correct
12 Correct 829 ms 99152 KB Output is correct
13 Correct 527 ms 99224 KB Output is correct
14 Correct 395 ms 99168 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 604 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Incorrect 0 ms 348 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -