Submission #602988

#	Time	Username	Problem	Language	Result	Execution time	Memory
602988		mosiashvililuka	Toy Train (IOI17_train)	C++14	100 / 100	619 ms	3484 KiB

train

#include<bits/stdc++.h>
#include "train.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[5009],g[5009],k[5009],boA[5009],boB[5009],bo[5009],p[5009],pi;
vector <int> S,X,ans;
set <int> v[5009],V[5009];
void adA(int q){
    for(set <int>::iterator it=V[q].begin(); it!=V[q].end(); it++){
        //if(bo[(*it)]==1) continue;
        if(boA[(*it)]==1) continue;
        if(f[(*it)]==1){
            boA[(*it)]=1;
            S.push_back((*it));
        }else{
            k[(*it)]--;
            if(k[(*it)]==0){
                boA[(*it)]=1;
                S.push_back((*it));
            }
        }
    }
}
void adB(int q){
    for(set <int>::iterator it=V[q].begin(); it!=V[q].end(); it++){
        //if(bo[(*it)]==1) continue;
        if(boB[(*it)]==1) continue;
        if(f[(*it)]==0){
            boB[(*it)]=1;
            X.push_back((*it));
        }else{
            k[(*it)]--;
            if(k[(*it)]==0){
                boB[(*it)]=1;
                X.push_back((*it));
            }
        }
    }
}
vector<int> who_wins(std::vector<int> Aa, std::vector<int> Rr, std::vector<int> Uu, std::vector<int> Vv) {
    a=Aa.size();b=Uu.size();
    for(i=1; i<=a; i++) f[i]=Aa[i-1];
    for(i=1; i<=a; i++) g[i]=Rr[i-1];
    for(i=0; i<b; i++){
        Uu[i]++;Vv[i]++;
        v[Uu[i]].insert(Vv[i]);
        V[Vv[i]].insert(Uu[i]);
    }
    while(1){
    //
    S.clear();X.clear();
    for(i=1; i<=a; i++){
        /*if(bo[i]==0){
            boA[i]=boB[i]=0;
        }else{
            boA[i]=boB[i]=1;
        }*/
        boA[i]=boB[i]=0;
    }
    for(i=1; i<=a; i++){
        if(bo[i]==1) continue;
        k[i]=v[i].size();
    }
    for(i=1; i<=a; i++){
        if(bo[i]==1) continue;
        if(g[i]==1){
            S.push_back(i);boA[i]=1;
        }
    }
    for(ii=0; ii<S.size(); ii++){
        adA(S[ii]);
    }
    for(i=1; i<=a; i++){
        if(bo[i]==1) continue;
        if(boA[i]==0){
            X.push_back(i);boB[i]=1;
        }
    }
    for(i=1; i<=a; i++){
        if(bo[i]==1) continue;
        k[i]=v[i].size();
    }
    for(ii=0; ii<X.size(); ii++){
        adB(X[ii]);
    }
    if(X.size()==0){
        for(i=1; i<=a; i++){
            if(bo[i]==0) ans.push_back(1); else ans.push_back(0);
        }
        return ans;
    }
    for(ii=0; ii<X.size(); ii++){
        i=X[ii];
        for(set <int>::iterator it=v[i].begin(); it!=v[i].end(); it++){
            V[(*it)].erase(V[(*it)].find(i));
        }
        v[i].clear();
        for(set <int>::iterator it=V[i].begin(); it!=V[i].end(); it++){
            v[(*it)].erase(v[(*it)].find(i));
        }
        V[i].clear();
    }
    for(ii=0; ii<X.size(); ii++){
        i=X[ii];
        bo[i]=1;
    }
    //
    }
}

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:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(ii=0; ii<S.size(); ii++){
      |               ~~^~~~~~~~~
train.cpp:82:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(ii=0; ii<X.size(); ii++){
      |               ~~^~~~~~~~~
train.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(ii=0; ii<X.size(); ii++){
      |               ~~^~~~~~~~~
train.cpp:102:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(ii=0; ii<X.size(); ii++){
      |               ~~^~~~~~~~~

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