oj.uz

답안 #1037596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1037596 2024-07-29T05:30:16 Z sleepntsheep 장난감 기차 (IOI17_train) C++17
27 / 100
 1026 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(a[i]==1){
                for(int j=0;j<n;++j) if(j!=i&&dp[i][j]+dp[j][i]>0) go[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:159:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |                     if(goable==g[u].size())go[u]=1;
      |                        ~~~~~~^~~~~~~~~~~~~
train.cpp:160:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |                     else if(ungoable+goable==g[u].size())/*no unsure in v*/go[u]=0;
      |                             ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
train.cpp:166:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |             if(cnt2==unsure.size())assert(0);
      |                ~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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 512 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 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 99152 KB Output is correct
2 Correct 244 ms 99432 KB Output is correct
3 Correct 245 ms 99156 KB Output is correct
4 Correct 719 ms 99232 KB Output is correct
5 Correct 564 ms 99220 KB Output is correct
6 Correct 436 ms 99184 KB Output is correct
7 Correct 396 ms 99152 KB Output is correct
8 Correct 313 ms 99152 KB Output is correct
9 Correct 275 ms 99152 KB Output is correct
10 Correct 376 ms 99184 KB Output is correct
11 Correct 323 ms 99156 KB Output is correct
12 Correct 67 ms 99104 KB Output is correct
13 Correct 722 ms 99372 KB Output is correct
14 Correct 727 ms 99408 KB Output is correct
15 Correct 745 ms 99156 KB Output is correct
16 Correct 671 ms 99224 KB Output is correct
17 Correct 697 ms 99216 KB Output is correct
18 Correct 322 ms 99156 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 672 ms 98900 KB Output is correct
2 Correct 334 ms 98900 KB Output is correct
3 Correct 392 ms 99156 KB Output is correct
4 Correct 538 ms 99220 KB Output is correct
5 Correct 528 ms 99208 KB Output is correct
6 Correct 448 ms 99156 KB Output is correct
7 Correct 470 ms 99152 KB Output is correct
8 Correct 411 ms 99180 KB Output is correct
9 Correct 91 ms 98904 KB Output is correct
10 Correct 866 ms 99412 KB Output is correct
11 Correct 827 ms 99220 KB Output is correct
12 Correct 898 ms 99228 KB Output is correct
13 Correct 634 ms 99160 KB Output is correct
14 Correct 431 ms 99152 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1026 ms 201436 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 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 512 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 600 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 -