제출 #265392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
265392		alexandra_udristoiu	Toy Train (IOI17_train)	C++14	100 / 100	475 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){
            for(i = 0; i < n; i++){
                viz[i] = 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) );
        memset(viz3, 0, sizeof(viz3) );
        p = 1;
        u = 0;
        ok = 1;
        for(i = 0; i < n; i++){
            if(viz[i] == 0 || viz2[i] == 0){
                if(viz[i] == 1){
                    ok = 0;
                }
                c[++u] = i;
                viz[i] = 0;
                viz3[i] = 1;
            }
        }
        if(ok == 1){
            break;
        }
        while(p <= u){
            nod = c[p];
            p++;
            for(i = 0; i < v[nod].size(); i++){
                vecin = v[nod][i];
                if(viz[vecin] == 1 && viz3[vecin] == 0){
                    g[vecin]++;
                    if(a[vecin] == 0 || g[vecin] == grad[vecin]){
                        c[++u] = vecin;
                        viz[vecin] = 0;
                        viz3[vecin] = 1;
                    }
                }
            }
        }
    }
    for(i = 0; i < n; i++){
        sol[i] = viz[i];
    }
    return sol;
}

컴파일 시 표준 에러 (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:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for(i = 0; i < v[nod].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~
train.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             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;
      |            ^

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