Submission #265109

#	Time	Username	Problem	Language	Result	Execution time	Memory
265109		alexandra_udristoiu	Toy Train (IOI17_train)	C++14	16 / 100	56 ms	1536 KiB

train

#include<iostream>
#include<vector>
#include<cstring>
#include "train.h"
using namespace std;
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> X, vector<int> Y){
    int i, j, n, ok, p, u, nod, vecin;
    vector<int> v[5005], sol;
    int viz[5005], viz2[5005], c[5005], g[5005], viz3[5005], grad[5005];
    n = a.size();
    sol.resize(n);
    for(i = 0; i < X.size(); i++){
        v[ Y[i] ].push_back(X[i]);
        grad[ X[i] ]++;
    }
    for(i = 0; i < n; i++){
        viz[i] = 1;
    }
    while(1){
        memset(viz2, 0, sizeof(viz2) );
        memset(g, 0, sizeof(g) );
        p = 1;
        u = 0;
        for(i = 0; i < n; i++){
            if(viz[i] == 1 && r[i] == 1){
                c[++u] = i;
                viz2[i] = 1;
            }
        }
        if(u == 0){
            break;
        }
        while(p <= u){
            nod = c[p];
            p++;
            for(i = 0; i < v[nod].size(); i++){
                vecin = v[nod][i];
                if(viz2[vecin] == 0 && viz[vecin] == 1){
                    g[vecin]++;
                    if(a[vecin] == 1 || g[vecin] == grad[vecin]){
                        c[++u] = vecin;
                        viz2[vecin] = 1;
                    }
                }
            }
        }
        memset(g, 0, sizeof(g) );
        p = 1;
        u = 0;
        for(i = 0; i < n; i++){
            if(viz[i] == 1 && viz2[i] == 0){
                c[++u] = i;
                viz[i] = 0;
            }
        }
        if(u == 0){
            break;
        }
        while(p <= u){
            nod = c[p];
            p++;
            for(i = 0; i < v[nod].size(); i++){
                vecin = v[nod][i];
                if(viz[vecin] == 1){
                    g[vecin]++;
                    if(a[vecin] == 0 || g[vecin] == grad[vecin]){
                        c[++u] = vecin;
                        viz[vecin] = 0;
                    }
                }
            }
        }
    }
    for(i = 0; i < n; i++){
        sol[i] = viz[i];
    }
    return sol;
}

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:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(i = 0; i < X.size(); i++){
      |                ~~^~~~~~~~~~
train.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for(i = 0; i < v[nod].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~
train.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(i = 0; i < v[nod].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~
train.cpp:7:12: warning: unused variable 'j' [-Wunused-variable]
    7 |     int i, j, n, ok, p, u, nod, vecin;
      |            ^
train.cpp:7:18: warning: unused variable 'ok' [-Wunused-variable]
    7 |     int i, j, n, ok, p, u, nod, vecin;
      |                  ^~
train.cpp:9:50: warning: unused variable 'viz3' [-Wunused-variable]
    9 |     int viz[5005], viz2[5005], c[5005], g[5005], viz3[5005], grad[5005];
      |                                                  ^~~~

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