oj.uz

Submission #56263

# Submission time Handle Problem Language Result Execution time Memory
56263 2018-07-10T18:31:53 Z ngkan146 Toy Train (IOI17_train) C++11
0 / 100
 614 ms 39748 KB 
#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;
            -- deg[v];
            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;
            -- deg[v];
            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++){
        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

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: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:85:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++)
              ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1404 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1404 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 614 ms 39748 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 39748 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 39748 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1404 KB secret mismatch
2 Halted 0 ms 0 KB -