Submission #1037607

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1037607	2024-07-29 05:50:21	sleepntsheep	Toy Train (IOI17_train)	C++17	27 / 100	1025 ms	201436 KiB

train

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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; }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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