Submission #1037607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037607		sleepntsheep	Toy Train (IOI17_train)	C++17	27 / 100	1025 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 c[3]={0};
                for(int v:g[u]) ++c[go[v]];
                if(a[u]){
                    if(c[1])go[u]=1;
                    else if(c[2]==0)go[u]=0;
                }else{
                    if(c[0]+c[2]==0)go[u]=1;
                    else if(c[0])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:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             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