Submission #1037631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037631		12345678	Toy Train (IOI17_train)	C++17	10 / 100	640 ms	1372 KiB

train

#include "train.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=20;

int n, R[nx], A[nx];
vector<int> d[nx];

int solve(int u, vector<int> p)
{
    int a=0, b=0;
    for (auto v:d[u])
    {
        int in=0;
        for (int i=0; i<p.size(); i++) if (p[i]==v) in=1;
        if (in)
        {
            int pw=R[v];
            vector<int> tmp=p;
            while (tmp.back()!=v) pw=pw||R[tmp.back()], tmp.pop_back();
            if (pw) a++;
            else b++;
        }
        else
        {
            p.push_back(v);
            if (solve(v, p)) a++;
            else b++;
            p.pop_back();
        }
    }
    if (A[u])
    {
        if (a>0) return 1;
        else return 0;
    }
    else
    {
        if (b>0) return 0;
        else return 1;
    }
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    n=a.size();
    vector<int> res(n);
    for (int i=0; i<n; i++) R[i]=r[i], A[i]=a[i];
    for (int i=0; i<u.size(); i++) d[u[i]].push_back(v[i]);
    for (int i=0; i<n; i++) res[i]=solve(i, vector<int> {i});
    return res;
}

Compilation message (stderr)

train.cpp: In function 'int solve(int, std::vector<int>)':
train.cpp:17:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for (int i=0; i<p.size(); i++) if (p[i]==v) in=1;
      |                       ~^~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i=0; i<u.size(); i++) d[u[i]].push_back(v[i]);
      |                   ~^~~~~~~~~

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