oj.uz

Submission #284527

# Submission time Handle Problem Language Result Execution time Memory
284527 2020-08-27T14:47:59 Z evpipis Toy Train (IOI17_train) C++11
28 / 100
 719 ms 1656 KB 
#include <bits/stdc++.h>
#include "train.h"

using namespace std;

#define pb push_back
typedef vector<int> vi;

const int len = 5005;
int vis[len], block[len], bel[len], deg[len], n;
vector<int> adj[len];

void print(vi vec){
    for (int i = 0; i < vec.size(); i++)
        printf(" %d", vec[i]);
    printf("\n");
}

vi operator-(vi a, vi b){
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vi res;
    for (int i = 0, j = 0; i < a.size(); i++){
        while (j < b.size() && b[j] < a[i])
            j++;

        if (j == b.size() || b[j] > a[i])
            res.pb(a[i]);
    }

    return res;
}

vi func(int sub, vi base){
    //printf("ins func: sub = %d, base =", sub), print(base);
    for (int u = 0; u < n; u++)
        vis[u] = deg[u] = 0;
    for (int u = 0; u < n; u++){
        if (block[u]) continue;

        for (auto v: adj[u])
            if (!block[v])
                deg[v]++;
    }

    //for (int u = 0; u  < n; u++)
      //  printf("u = %d, deg = %d\n", u, deg[u]);

    queue<int> myq;
    for (auto u: base)
        vis[u] = 1, myq.push(u);

    while (!myq.empty()){
        int u = myq.front();
        myq.pop();

        for (auto v: adj[u]){
            if (block[v] || vis[v])
                continue;

            if (bel[v] == sub)
                vis[v] = 1, myq.push(v);
            else{
                deg[v]--;
                if (!deg[v])
                    vis[v] = 1, myq.push(v);
            }
        }
    }

    vi res;
    for (int i = 0; i < n; i++)
        if (!block[i] && vis[i])
            res.pb(i);
    //printf("and res ="), print(res);
    return res;
}

vi who_wins(vi B, vi spec, vi U, vi V) {
    n = B.size();

    for (int i = 0; i < U.size(); i++){
        int a = U[i], b = V[i];
        adj[b].pb(a);
    }

    vi graph;
    for (int i = 0; i < n; i++)
        graph.pb(i), block[i] = 0, bel[i] = B[i];

    while (true){
        vi reach, rest;

        for (auto u: graph)
            if (spec[u])
                reach.pb(u);

        reach = func(1, reach);
        rest = func(0, graph-reach);

        /*printf("graph:"), print(graph);
        printf("reach:"), print(reach);
        printf("rest:"), print(rest);*/

        if (rest.size() == 0)
            break;

        graph = graph-rest;
    }

    vi res(n, 0);
    for (auto u: graph)
        res[u] = 1;
	return res;
}
/*
3 6
1 0 0
0 1 0
0 0
0 1
1 0
1 2
2 2
2 1
*/

Compilation message

train.cpp: In function 'void print(vi)':
train.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < vec.size(); i++)
      |                     ~~^~~~~~~~~~~~
train.cpp: In function 'vi operator-(vi, vi)':
train.cpp:24:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0, j = 0; i < a.size(); i++){
      |                            ~~^~~~~~~~~~
train.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         while (j < b.size() && b[j] < a[i])
      |                ~~^~~~~~~~~~
train.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if (j == b.size() || b[j] > a[i])
      |             ~~^~~~~~~~~~~
train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < U.size(); i++){
      |                     ~~^~~~~~~~~~
train.cpp:113:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  113 |     for (auto u: graph)
      |     ^~~
train.cpp:115:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  115 |  return res;
      |  ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1024 KB Output is correct
2 Correct 12 ms 1024 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct
5 Correct 7 ms 1024 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 5 ms 1024 KB Output is correct
8 Correct 7 ms 1024 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 5 ms 1024 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Incorrect 1 ms 512 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 1656 KB Output is correct
2 Correct 533 ms 1564 KB Output is correct
3 Correct 719 ms 1536 KB Output is correct
4 Correct 10 ms 1408 KB Output is correct
5 Incorrect 11 ms 1532 KB 3rd lines differ - on the 11th token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1280 KB Output is correct
2 Correct 13 ms 1408 KB Output is correct
3 Correct 9 ms 1408 KB Output is correct
4 Correct 11 ms 1512 KB Output is correct
5 Correct 10 ms 1536 KB Output is correct
6 Correct 10 ms 1408 KB Output is correct
7 Correct 14 ms 1408 KB Output is correct
8 Correct 9 ms 1408 KB Output is correct
9 Correct 9 ms 1408 KB Output is correct
10 Correct 9 ms 1440 KB Output is correct
11 Correct 9 ms 1520 KB Output is correct
12 Correct 11 ms 1408 KB Output is correct
13 Correct 10 ms 1408 KB Output is correct
14 Correct 9 ms 1408 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1564 KB Output is correct
2 Correct 11 ms 1408 KB Output is correct
3 Correct 10 ms 1408 KB Output is correct
4 Correct 8 ms 1408 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 7 ms 1024 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 6 ms 1024 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1024 KB Output is correct
2 Correct 12 ms 1024 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct
5 Correct 7 ms 1024 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 5 ms 1024 KB Output is correct
8 Correct 7 ms 1024 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 5 ms 1024 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 0 ms 512 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Incorrect 1 ms 512 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
20 Halted 0 ms 0 KB -