Submission #1069945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069945		new_acc	Toy Train (IOI17_train)	C++14	100 / 100	1038 ms	6488 KiB

train

#include "train.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
const int N=1e5+10;
int t[N],t2[N],n,m,il[N];
vi graf[N],graf2[N];
bool byl[N];
vi who_wins(vi a,vi r,vi u,vi v) {
    n=a.size(),m=u.size();
    vi res(n,1);
    for(int i=1;i<=n;i++) t[i]=a[i-1],t2[i]=r[i-1];
    for(int i=1;i<=m;i++){
        graf[u[i-1]+1].push_back(v[i-1]+1);
        graf2[v[i-1]+1].push_back(u[i-1]+1);
    }
    for(int i2=0;i2<n;i2++){
    for(int i=1;i<=n;i++) il[i]=graf[i].size();
    vi curr; 
    for(int i=1;i<=n;i++){
        if(t2[i] and res[i-1]) curr.push_back(i),byl[i]=1;
        else byl[i]=0;
    }
    for(int i=0;i<curr.size();i++){
        int x=curr[i];
        for(auto u:graf2[x]){
            if(t[u]){
                if(!byl[u]) curr.push_back(u);
                byl[u]=1;
            }else{
                il[u]--;
                if(il[u]==0 and !byl[u]){
                    byl[u]=1;
                    curr.push_back(u);
                }
            }
        }
    }
    curr.clear();
    for(int i=1;i<=n;i++){
        if(!byl[i]){
            curr.push_back(i);
            byl[i]=1;
        }else byl[i]=0;
        il[i]=graf[i].size();
    }
    for(int i=0;i<curr.size();i++){
        int x=curr[i];
        res[x-1]=0;
        for(auto u:graf2[x]){
            if(!t[u]){
                if(!byl[u]){
                    byl[u]=1;
                    curr.push_back(u);
                }
            }else{
                il[u]--;
                if(il[u]==0 and !byl[u]){
                    byl[u]=1;
                    curr.push_back(u);
                }
            }
        }
    }
    }
    return res;
}

Compilation message (stderr)

train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<curr.size();i++){
      |                 ~^~~~~~~~~~~~
train.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<curr.size();i++){
      |                 ~^~~~~~~~~~~~

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