Submission #593460

#	Time	Username	Problem	Language	Result	Execution time	Memory
593460		keta_tsimakuridze	Toy Train (IOI17_train)	C++14	0 / 100	9 ms	1236 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int f[N], out[N], vis[N], a[N];
vector<int> in[N];
void go(vector<int> cur, int t) {
        while(cur.size()) {
            int u = cur.back();
            cur.pop_back();
            for(int i = 0; i < in[u].size(); i++) {
                int v = in[u][i];
                if(vis[v] || f[v]) continue;
                out[v]--;
                if(a[v] == t || !out[v]) vis[v] = 1, cur.push_back(v);
            }
        }
}
std::vector<int> who_wins(std::vector<int> A, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    int n = A.size(), m = v.size();
    vector<int> w(n);

    for(int i = 0; i < n; i++) w[i] = 1, a[i] = A[i], in[i].clear();
    for(int i = 0; i < m; i++) in[v[i]].push_back(u[i]);
    while(true) {
        for(int i = 0; i < n; i++) vis[i] = 0, out[i] = 0;
        for(int i = 0; i < m; i++) ++out[u[i]];

        vector<int> cur;
        for(int i = 0; i < r.size(); i++) {
            if(!f[r[i]]) {
                cur.push_back(r[i]);
                vis[r[i]] = 1;
            }
        }
        go(cur, 1);
        int F = 0;
        for(int i = 0; i < n; i++) {
            if(!f[i] && !vis[i]) {
                f[i] = 1;
                F = 1;
            }
        }
        if(!F) break;
        cur.clear();
        for(int i = 0; i < n; i++) vis[i] = 0, out[i] = 0;
        for(int i = 0; i < m; i++) ++out[u[i]];

        for(int i = 0; i < n; i++) {
            if(f[i]) cur.push_back(i), vis[i] = 1;
        }
        go(cur, 0);
        for(int i = 0; i < n; i++) {
            f[i] = vis[i];
            w[i] = 1 - f[i];
        }
    }
    return w;
}

Compilation message (stderr)

train.cpp: In function 'void go(std::vector<int>, int)':
train.cpp:11:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |             for(int i = 0; i < in[u].size(); i++) {
      |                            ~~^~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int i = 0; i < r.size(); i++) {
      |                        ~~^~~~~~~~~~

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