oj.uz

Submission #555815

# Submission time Handle Problem Language Result Execution time Memory
555815 2022-05-01T15:30:04 Z Lemur95 Toy Train (IOI17_train) C++17
11 / 100
 300 ms 1748 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <chrono>
#include <cassert>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <random>
#include "train.h"

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#  define __builtin_popcountll __popcnt64
#endif

//#pragma GCC optimize("Ofast")
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define x first
#define y second
#define ld long double
#define ll long long
#define ull unsigned long long
#define us unsigned short
#define lsb(x) ((x) & (-(x)))
#define pii pair <int, int>
#define pll pair <ll, ll>

using namespace std;

ifstream in("test.in");
ofstream out("test.out");

mt19937 gen(time(0));
uniform_int_distribution <uint32_t> rng;

const int MOD = (int)1e9 + 7;

ll gcd(ll a, ll b) {
    if (!b)
        return a;
    return gcd(b, a % b);
}

int n, m;

int s[200005], f[200005];
int st[200005];
ll dp[200005];

vector <int> who_wins(vector <int> a, vector <int> r, vector <int> u, vector <int> v) {
    n = a.size(), m = u.size();

    vector <int> g[5005], gr[5005];
    vector <int> in(n);

    for (int i = 0; i < m; i++) {
        g[u[i]].push_back(v[i]);
        gr[v[i]].push_back(u[i]);
    }

    while (true) {
        queue <int> q;
        vector <int> cnt(n);

        fill(cnt.begin(), cnt.end(), 0);
        vector <int> s = r;

        for (int i = 0; i < n; i++) {
            if (r[i])
                q.push(i);
        }

        while (!q.empty()) {
            int nod = q.front();
            q.pop();

            for (auto& fiu : gr[nod]) {
                cnt[fiu]++;

                if (!s[fiu]) {
                    if (a[fiu] && cnt[fiu]) {
                        s[fiu] = 1;
                        q.push(fiu);
                    }
                    else if (!a[fiu] && cnt[fiu] == g[fiu].size()) {
                        s[fiu] = 1;
                        q.push(fiu);
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (!s[i])
                q.push(i);
            s[i] ^= 1;
        }

        while (!q.empty()) {
            int nod = q.front();
            q.pop();

            for (auto& fiu : gr[nod]) {
                cnt[fiu]++;

                if (!s[fiu]) {
                    if (!a[fiu] && cnt[fiu]) {
                        s[fiu] = 1;
                        q.push(fiu);
                    }
                    else if (a[fiu] && cnt[fiu] == g[fiu].size()) {
                        s[fiu] = 1;
                        q.push(fiu);
                    }
                }
            }
        }

        bool flag = 1;
        for (int i = 0; i < n; i++) {
            if (r[i] && s[i])
                r[i] = 0, flag = 0;
        }

        if (flag) {
            vector <int> ans(n);

            for (int i = 0; i < n; i++)
                ans[i] = s[i] ^ 1;

            return ans;
        }
    }
}

/*void solve() {
    int n, m;
    cin >> n >> m;

    vector <int> a(n), r(n), u(m), v(m);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }

    for (int i = 0; i < m; i++) {
        cin >> u[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> v[i];
    }

    vector <int> ans = who_wins(a, r, u, v);

    for (auto& i : ans)
        cout << i << " ";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    srand(time(0));

    int T = 1;

    //cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}*/

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:95:50: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                     else if (!a[fiu] && cnt[fiu] == g[fiu].size()) {
train.cpp:121:49: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |                     else if (a[fiu] && cnt[fiu] == g[fiu].size()) {

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1236 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 1684 KB Output is correct
2 Correct 203 ms 1748 KB Output is correct
3 Correct 300 ms 1744 KB Output is correct
4 Incorrect 10 ms 1624 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1408 KB Output is correct
2 Correct 8 ms 1508 KB Output is correct
3 Correct 9 ms 1652 KB Output is correct
4 Correct 9 ms 1628 KB Output is correct
5 Correct 8 ms 1604 KB Output is correct
6 Correct 8 ms 1604 KB Output is correct
7 Correct 10 ms 1612 KB Output is correct
8 Correct 7 ms 1620 KB Output is correct
9 Correct 8 ms 1492 KB Output is correct
10 Correct 9 ms 1628 KB Output is correct
11 Correct 8 ms 1620 KB Output is correct
12 Correct 9 ms 1620 KB Output is correct
13 Correct 8 ms 1624 KB Output is correct
14 Correct 8 ms 1492 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1620 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1236 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -