oj.uz

Submission #1037600

# Submission time Handle Problem Language Result Execution time Memory
1037600 2024-07-29T05:38:57 Z sleepntsheep Toy Train (IOI17_train) C++17
27 / 100
 1006 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(ungoable==g[u].size())go[u]=0;
                }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:156:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |                     else if(ungoable==g[u].size())go[u]=0;
      |                             ~~~~~~~~^~~~~~~~~~~~~
train.cpp:158:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |                     if(goable==g[u].size())go[u]=1;
      |                        ~~~~~~^~~~~~~~~~~~~
train.cpp:159:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |                     else if(ungoable+goable==g[u].size())/*no unsure in v*/go[u]=0;
      |                             ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
train.cpp:165:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |             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 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 512 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 508 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 234 ms 99432 KB Output is correct
2 Correct 239 ms 99220 KB Output is correct
3 Correct 257 ms 99232 KB Output is correct
4 Correct 779 ms 99156 KB Output is correct
5 Correct 619 ms 99224 KB Output is correct
6 Correct 485 ms 99156 KB Output is correct
7 Correct 452 ms 99412 KB Output is correct
8 Correct 325 ms 99212 KB Output is correct
9 Correct 301 ms 99408 KB Output is correct
10 Correct 376 ms 99180 KB Output is correct
11 Correct 350 ms 99408 KB Output is correct
12 Correct 73 ms 99164 KB Output is correct
13 Correct 787 ms 99228 KB Output is correct
14 Correct 754 ms 99224 KB Output is correct
15 Correct 749 ms 99312 KB Output is correct
16 Correct 694 ms 99136 KB Output is correct
17 Correct 750 ms 99216 KB Output is correct
18 Correct 318 ms 98896 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 98900 KB Output is correct
2 Correct 360 ms 98900 KB Output is correct
3 Correct 451 ms 99220 KB Output is correct
4 Correct 553 ms 98976 KB Output is correct
5 Correct 517 ms 99152 KB Output is correct
6 Correct 534 ms 99200 KB Output is correct
7 Correct 504 ms 99192 KB Output is correct
8 Correct 446 ms 99176 KB Output is correct
9 Correct 86 ms 98900 KB Output is correct
10 Correct 883 ms 99024 KB Output is correct
11 Correct 807 ms 99156 KB Output is correct
12 Correct 887 ms 99160 KB Output is correct
13 Correct 582 ms 99192 KB Output is correct
14 Correct 437 ms 99412 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1006 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 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 512 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 508 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 -