Submission #56262

#	Time	Username	Problem	Language	Result	Execution time	Memory
56262		ngkan146	Toy Train (IOI17_train)	C++11	0 / 100	520 ms	41300 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define AREZOU 1
#define BORZOU 0

int n, m;
vector <int> G[5005];
vector <int> Gback[5005];
int owner[5005];
int chargingStation[5005];
int result[5005];
int deg[5005];

bool curVer[5005], visited[5005], ok[5005], del[5005];
void solve(vector <int> lst){
    for(auto v: lst)    cout << v << ' '; cout << endl;
    memset(curVer, 0, sizeof(curVer));
    memset(visited, 0, sizeof(visited));
    memset(ok, 0, sizeof(ok));

    for(auto u: lst){
        ok[u] = 1;
        curVer[u] = 1;
        for(auto v: Gback[u]){
            if (curVer[v])  deg[v] ++;
        }
    }

    vector <int> goodForArezou;
    vector <int> goodForBorzou;
    queue <int> q;

    for(auto v: lst)
        if (chargingStation[v]) q.push(v), visited[v] = 1;

    while(q.size()){
        int u = q.front();
        q.pop();
        goodForArezou.push_back(u);
        for(auto v: Gback[u]){
            if (!curVer[v]) continue;
            if (!visited[v] && owner[v] == AREZOU || !(--deg[v])){
                visited[v] = 1;
                q.push(v);
            }
        }
    }

    for(auto v: goodForArezou)  ok[v] = 0;
    memset(visited, 0, sizeof(visited));
    for(int i=0;i<n;i++){
        deg[i] = 0;
        if (ok[i])  q.push(i), visited[i] = 1;
    }
    for(auto u: lst){
        for(auto v: Gback[u]){
            if (curVer[v])  deg[v] ++;
        }
    }
    while(q.size()){
        int u = q.front();
        q.pop();
        goodForBorzou.push_back(u);
        for(auto v: Gback[u]){
            if (!curVer[v]) continue;
            if (!visited[v] && owner[v] == BORZOU || !(--deg[v])){
                visited[v] = 1;
                q.push(v);
            }
        }
    }

    for(auto v: goodForBorzou)  del[v] = 1;
    vector <int> newLst;
    for(int i=0;i<n;i++)    if (!del[i])    newLst.push_back(i);
    if (lst == newLst) {for(auto v: lst) result[v] = 1; return;}
    solve(newLst);
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) {
	n = A.size();
	for(int i=0;i<A.size();i++)
        owner[i] = A[i],
        chargingStation[i] = R[i];
    m = U.size();
    for(int i=0;i<m;i++){
        G[U[i]].push_back(V[i]);
        Gback[V[i]].push_back(U[i]);
    }
    vector <int> lst;
    for(int i=0;i<n;i++)    lst.push_back(i);
    solve(lst);
    vector <int> res;
    for(int i=0;i<n;i++)    res.push_back(result[i]);
    return res;
}
/*
2 4
0 1
1 0
0 0
0 1
1 0
1 1
*/

Compilation message (stderr)

train.cpp: In function 'void solve(std::vector<int>)':
train.cpp:17:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto v: lst)    cout << v << ' '; cout << endl;
     ^~~
train.cpp:17:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(auto v: lst)    cout << v << ' '; cout << endl;
                                           ^~~~
train.cpp:43:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if (!visited[v] && owner[v] == AREZOU || !(--deg[v])){
                             ^
train.cpp:67:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if (!visited[v] && owner[v] == BORZOU || !(--deg[v])){
                             ^
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.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