Submission #314422

#	Time	Username	Problem	Language	Result	Execution time	Memory
314422		hhh07	Toy Train (IOI17_train)	C++14	0 / 100	9 ms	1512 KiB

train

#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include "train.h"

using namespace std;

typedef long long ll;
typedef vector<int> vi;

vector<vi> adjList(5005, vi());
vi gotov(5005, false), t;
int n;

vi operator-(vi a, vi b){
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    vi res; int j = 0;
    for (int i = 0; i < a.size(); i++){
        while(j < b.size() && b[j] < a[i])
            j++;
        
        if (j == b.size() || b[j] > a[i])
            res.push_back(a[i]);
    }
    
    return res;
}

int vis[5005], deg[5005];

vi f(bool type, vi x){
    for (int i = 0; i < n; i++)
        vis[i] = deg[i] = 0;
    
    for (int i = 0; i < n; i++){
        if (gotov[i])
            continue;
        for (int j = 0; j < adjList[i].size(); j++){
            int curr = adjList[i][j];
            if (!gotov[curr])
                deg[curr]++;
        }
    }
    
    queue<int> q;
    for (int i = 0; i < x.size(); i++)
        vis[x[i]] = true, q.push(x[i]);
    
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        for (int i = 0; i < adjList[curr].size(); i++){
            int k = adjList[curr][i];
            if (gotov[k] || vis[k])
                continue;
            if (t[k] == type)
                vis[k] = true, q.push(k);
            else{
                deg[k]--;
                if (!deg[k])
                    vis[k] = true, q.push(k);
            }
        }
    }
    
    vi res;
    for (int i = 0; i < n; i++){
        if (!gotov[i] && vis[i])
            res.push_back(i);
    }
    return res;
}

vi who_wins(vi a, vi r, vi u, vi v){
    n = a.size(); int m = u.size();
    t = a;
    for (int i = 0; i < m; i++)
        adjList[u[i]].push_back(v[i]);
    
    vi graph;
    for (int i = 0; i < n; i++)
        graph.push_back(i);
    
    while(!graph.empty()){
        vi f_a, f_b;
        
        for (int i = 0; i < graph.size(); i++)
            if (r[graph[i]])
                f_a.push_back(i);
            
        f_a = f(1, f_a); f_b = f(0, graph - f_a);
        
        if (!f_b.size())
            break;
        
        for (int i = 0; i < f_b.size(); i++)
            gotov[f_b[i]] = true;
        
        graph = graph - f_b;
    }
    
    vi res(n, 0);
    for (int i = 0; i < graph.size(); i++)
        res[graph[i]] = true;
    return res;
}

Compilation message (stderr)

train.cpp: In function 'vi operator-(vi, vi)':
train.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < a.size(); i++){
      |                     ~~^~~~~~~~~~
train.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         while(j < b.size() && b[j] < a[i])
      |               ~~^~~~~~~~~~
train.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if (j == b.size() || b[j] > a[i])
      |             ~~^~~~~~~~~~~
train.cpp: In function 'vi f(bool, vi)':
train.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int j = 0; j < adjList[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~~~~
train.cpp:50:23: 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 < x.size(); i++)
      |                     ~~^~~~~~~~~~
train.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < adjList[curr].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~
train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int i = 0; i < graph.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
train.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (int i = 0; i < f_b.size(); i++)
      |                         ~~^~~~~~~~~~~~
train.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 0; i < graph.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