Submission #1070783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070783		Ahmed57	Toy Train (IOI17_train)	C++17	23 / 100	166 ms	1572 KiB

train

#include "bits/stdc++.h"
 
using namespace std;
vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v){
    int n = a.size();
    int m = u.size();
    vector<int> adj[n+1],rev[n+1];
    for(int i = 0;i<u.size();i++){
        adj[u[i]].push_back(v[i]);
        rev[v[i]].push_back(u[i]);
    }
    vector<int> ans(n,1);
    int deg[n+1] = {0};
    int vis[n+1] = {0};
    int ch[n+1] = {0};
    while(1){
        for(int i = 0;i<n;i++){
            if(ans[i]){
                vis[i] = 0;ch[i] = 0;
                deg[i] = 0;
                for(auto j:adj[i]){
                    if(ans[j])deg[i]++;
                }
            }
        }
        queue<int> q;
        for(int i = 0;i<n;i++){
            if(ans[i]&&r[i]){
                q.push(i);
            }
        }
        while(!q.empty()){
            int x = q.front();q.pop();
            if(ch[x])continue;
            ch[x] = 1;
            for(auto i:rev[x]){
                deg[i]--;
                if(ans[i]&&(deg[i]==0||a[i]==1)&&!vis[i]){
                    vis[i] = 1;
                    q.push(i);
                }
            }
        }
        bool upd = 0;
        for(int i = 0;i<n;i++){
            int old = ans[i];
            ans[i]&=vis[i];
            if(old!=ans[i])upd = 1;
        }
        if(upd==0)break;
    }
    return ans;
}

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:8:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for(int i = 0;i<u.size();i++){
      |                   ~^~~~~~~~~
train.cpp:6:9: warning: unused variable 'm' [-Wunused-variable]
    6 |     int m = u.size();
      |         ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 12 / 12
• Subtask 6: 0 / 51