oj.uz

Submission #295906

# Submission time Handle Problem Language Result Execution time Memory
295906 2020-09-10T05:55:11 Z Trickster Toy Train (IOI17_train) C++14
0 / 100
 2000 ms 4728 KB 
#include "train.h"
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define N 100010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) int(a.size())
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int n, m;
int vis[N];
int Ch[N];
map <pii, int> M;
vector <int> E[N], v, c;

void dfs(int nd, int pr)
{
    v.pb(nd);
    vis[nd] = vis[pr]+1;
    if(Ch[nd] == 1) c.pb(nd);

    for(auto i: E[nd]) {
        if(vis[i]) {
            int ok = 1;
            if(vis[c.back()] < vis[i]) ok = 0; 

            v.pb(i);
            for(int h = 0; h < v.size()-1; h++) {
                if(vis[v[h]] < vis[i]) continue;

                M[{v[h], v[h+1]}] = max(ok, M[{v[h], v[h+1]}]);
            }
            v.pop_back();

            continue;
        }

        dfs(i, nd);
    }

    vis[nd] = 0;
    v.pop_back();
    if(Ch[nd] == 1) c.pop_back();
}

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

    for(int i = 0; i < n; i++) Ch[i] = r[i];

    for(int i = 0; i < m; i++) E[u[i]].pb(v[i]);

    dfs(0, -1);

    // for(int i = 0; i < m; i++)
    // 	cout << M[{u[i], v[i]}] << " ";

    int A[N];
    memset(A, 0, sizeof(A));
    for(int i = 0; i < n; i++) {
        if(a[i] == 1) continue;

        int ok = 1;
        for(auto h: E[i]) if(M[{i, h}] == 0) ok = 0;

        if(ok == 0)
            for(auto h: E[i]) M[{i, h}] = M[{h, i}] = 0;

        A[i] = ok;
    } 
    for(int i = 0; i < n; i++) {
        if(a[i] == 0) continue;

        int ok = 0;
        for(auto h: E[i]) if(M[{i, h}] == 1 || A[h] == 1) ok = 1;

        A[i] = ok;
    } 

    vector <int> ret;
    for(int i = 0; i < n; i++) ret.pb(A[i]);

    return ret;
}

Compilation message

train.cpp:23: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   23 | #pragma GCC optimization ("O3")
      | 
train.cpp:24: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   24 | #pragma GCC optimization ("unroll-loops")
      | 
train.cpp: In function 'void dfs(int, int)':
train.cpp:45:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(int h = 0; h < v.size()-1; h++) {
      |                            ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4728 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 3 ms 3072 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 Execution timed out 2024 ms 3408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 3836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 3836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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