Submission #1037599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037599		sleepntsheep	Toy Train (IOI17_train)	C++17	27 / 100	975 ms	201436 KiB

train

#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 (stderr)

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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51