oj.uz

Submission #1037599

# Submission time Handle Problem Language Result Execution time Memory
1037599 2024-07-29T05:36:12 Z sleepntsheep Toy Train (IOI17_train) C++17
27 / 100
 975 ms 201436 KB 
#include "train.h"
#include<cassert>
#include<numeric>
#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;
    int is_subtask_5 = accumulate(r.begin(),r.end(),0)==1;
    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;
    } else if (is_subtask_5) {
        vector<vector<int> > rg(n),g(n); vector<int>loop(n); for(int i=0;i<m;++i){g[u[i]].push_back(v[i]); rg[v[i]].push_back(u[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>go(n);
        //dp = blahj's distance */
        fill(go.begin(),go.end(),2);/*undecided*/

        int x=max_element(r.begin(),r.end())-r.begin();

        for(int i=0;i<n;++i){
            if(i==x)continue;
            if(dp[i][x]==1)go[i]=1;
            if(a[i]==1){
            }else{
                if(loop[i])go[i]=0;
                if(dp[i][x]==1e9) go[i]=0;
            }
        }

        go[x]=1;

        for(int i=0;i<=n;++i){
            vector<int>unsure;
            for(int j=0;j<n;++j)if(go[j]==2)unsure.push_back(j);
            for(int u:unsure){
                int goable=0,ungoable=0;
                for(int v:g[u]){
                    goable+=(go[v]==1);
                    ungoable+=(go[v]==0);
                }
                if(a[u]){
                    if(goable)go[u]=1;
                }else{
                    if(goable==g[u].size())go[u]=1;
                    else if(ungoable+goable==g[u].size())/*no unsure in v*/go[u]=0;
                }
            }

            int cnt2=0;
            for(int j=0;j<n;++j)cnt2+=go[j]==2;
            if(cnt2==unsure.size())assert(0);

        }
    }



    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:157:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |                     if(goable==g[u].size())go[u]=1;
      |                        ~~~~~~^~~~~~~~~~~~~
train.cpp:158:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |                     else if(ungoable+goable==g[u].size())/*no unsure in v*/go[u]=0;
      |                             ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
train.cpp:164:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |             if(cnt2==unsure.size())assert(0);
      |                ~~~~^~~~~~~~~~~~~~~

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 604 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 600 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 600 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 98996 KB Output is correct
2 Correct 248 ms 99156 KB Output is correct
3 Correct 243 ms 99480 KB Output is correct
4 Correct 755 ms 99156 KB Output is correct
5 Correct 633 ms 99224 KB Output is correct
6 Correct 473 ms 98996 KB Output is correct
7 Correct 410 ms 99040 KB Output is correct
8 Correct 321 ms 99152 KB Output is correct
9 Correct 283 ms 98996 KB Output is correct
10 Correct 364 ms 99152 KB Output is correct
11 Correct 319 ms 99172 KB Output is correct
12 Correct 69 ms 98896 KB Output is correct
13 Correct 748 ms 99020 KB Output is correct
14 Correct 754 ms 99228 KB Output is correct
15 Correct 768 ms 99156 KB Output is correct
16 Correct 738 ms 99224 KB Output is correct
17 Correct 743 ms 99216 KB Output is correct
18 Correct 342 ms 98896 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 98868 KB Output is correct
2 Correct 332 ms 99152 KB Output is correct
3 Correct 426 ms 98984 KB Output is correct
4 Correct 577 ms 99160 KB Output is correct
5 Correct 567 ms 99216 KB Output is correct
6 Correct 484 ms 98956 KB Output is correct
7 Correct 492 ms 99156 KB Output is correct
8 Correct 423 ms 99176 KB Output is correct
9 Correct 96 ms 99152 KB Output is correct
10 Correct 913 ms 99340 KB Output is correct
11 Correct 855 ms 99152 KB Output is correct
12 Correct 917 ms 99224 KB Output is correct
13 Correct 571 ms 99156 KB Output is correct
14 Correct 421 ms 99152 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 975 ms 201436 KB Execution killed with signal 6
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 604 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 600 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 600 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Incorrect 1 ms 348 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -