Submission #365493

#	Time	Username	Problem	Language	Result	Execution time	Memory
365493		denkendoemeer	Toy Train (IOI17_train)	C++14	100 / 100	563 ms	1900 KiB

train

#include<bits/stdc++.h>
#include "train.h"
using namespace std;
bool viz[5005],c[5005];
int nr[5005],f[5005];
vector<int>g[5005],g2[5005];
vector<int> who_wins(vector<int>a,vector<int>r,vector<int>u,vector<int>v)
{
    int i;
    for(i=0;i<u.size();i++){
        g[u[i]].push_back(v[i]);
        g2[v[i]].push_back(u[i]);
    }
    int n=a.size();
    for(i=0;i<n;i++)
        f[i]=1;
    while(1){
        for(i=0;i<n;i++)
            if (f[i]==1){
                viz[i]=0;
                c[i]=0;
                if (a[i]==1)
                    nr[i]=1;
                else
                    nr[i]=g[i].size();
            }
        queue<int>q;
        for(i=0;i<n;i++)
            if (r[i] && f[i]==1)
                q.push(i);
        while(!q.empty()){
            int nod=q.front();
            q.pop();
            if (c[nod]==1)
                continue;
            c[nod]=1;
            for(i=0;i<g2[nod].size();i++){
                int aux=g2[nod][i];
                --nr[aux];
                if (nr[aux]==0 && viz[aux]==0 && f[aux]==1){
                    q.push(aux);
                    viz[aux]=1;
                }
            }
        }
        bool ok=0;
        for(i=0;i<n;i++)
            if (f[i]==1 && viz[i]==0){
                f[i]=0;
                ok=1;
            }
        if (ok==0)
            break;
    }
    vector<int>ans;
    for(i=0;i<n;i++)
        ans.push_back(f[i]);
    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:10:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(i=0;i<u.size();i++){
      |             ~^~~~~~~~~
train.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(i=0;i<g2[nod].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