oj.uz

Submission #283172

# Submission time Handle Problem Language Result Execution time Memory
283172 2020-08-25T10:52:27 Z MKopchev Toy Train (IOI17_train) C++14
11 / 100
 1100 ms 3328 KB 
#include "train.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e4+42;

int nxt[nmax];

vector<int> adj[nmax],trav[nmax],adj_comp[nmax];

int n,owner[nmax],charge[nmax];

int rec(int node)//1-> A wins, 0-> B wins
{
    if(nxt[node]!=-1)
    {
        if(charge[node])return 1;

        int other=nxt[node];

        while(other!=node)
        {
            if(charge[other])return 1;

            other=nxt[other];
        }

        return 0;
    }

    for(auto k:adj[node])
    {
        nxt[node]=k;

        int mem=rec(k);

        nxt[node]=-1;

        if(mem==owner[node])return mem;
    }

    return !owner[node];
}

bool been[nmax];

stack<int> st;

void dfs(int node)
{
    if(been[node])return;

    been[node]=1;

    for(auto k:adj[node])
        dfs(k);

    st.push(node);
}

int pointer,comp[nmax];

int mem[nmax];

int charge_comp[nmax];

vector<int> seen={};

set< pair<int,int> > edges;

void dfs_trav(int node)
{
    if(comp[node])return;

    comp[node]=pointer;

    seen.push_back(node);

    //charge_comp[pointer]=charge_comp[pointer]|charge[node];

    for(auto k:trav[node])
        dfs_trav(k);
}

int win(int node)
{
    if(mem[node]!=-1)return mem[node];

    int ret=charge_comp[node];

    for(auto k:adj_comp[node])
        ret=ret|win(k);

    mem[node]=ret;

    return ret;
}

bool b_win[nmax];

bool test(int node)
{
    if(been[node])return 0;

    if(b_win[comp[node]])return 1;

    been[node]=1;

    for(auto k:adj[node])
        if(test(k))return 1;

    return 0;
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v)
{
    memset(mem,-1,sizeof(mem));

    memset(nxt,-1,sizeof(nxt));

    n=a.size();

    for(int i=0;i<a.size();i++)owner[i]=a[i];

    for(int i=0;i<r.size();i++)charge[i]=r[i];

    for(int i=0;i<u.size();i++)
        if(charge[u[i]]==0&&charge[v[i]]==0)
        {
            adj[u[i]].push_back(v[i]);
            trav[v[i]].push_back(u[i]);

            edges.insert({u[i],v[i]});
        }
    //B is owner of all
    for(int i=0;i<n;i++)
        if(been[i]==0)dfs(i);

    memset(been,0,sizeof(been));

    while(st.size())
    {
        seen={};

        int tp=st.top();

        //cout<<"tp= "<<tp<<endl;

        st.pop();

        if(been[tp])continue;

        pointer++;
        dfs_trav(tp);

        if(seen.size()>=2||(seen.size()==1&&edges.count({seen[0],seen[0]})))
        {
            b_win[pointer]=1;
        }
        //cout<<pointer<<" -> "<<b_win[pointer]<<endl;
    }

    for(int i=0;i<n;i++)adj[i]={};

    for(int i=0;i<u.size();i++)
        adj[u[i]].push_back(v[i]);

    vector<int> outp={};

    for(int i=0;i<n;i++)
    {
        memset(been,0,sizeof(been));
        outp.push_back(1-test(i));
    }
    /*
    for(int i=0;i<n;i++)
    {
        cout<<outp[i]<<" "<<rec(i)<<endl;
    }

    for(int i=0;i<n;i++)
        assert(rec(i)==outp[i]);
    */

    return outp;
}

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:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i=0;i<a.size();i++)owner[i]=a[i];
      |                 ~^~~~~~~~~
train.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=0;i<r.size();i++)charge[i]=r[i];
      |                 ~^~~~~~~~~
train.cpp:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
train.cpp:165:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1792 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 1152 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 88 ms 3320 KB Output is correct
2 Correct 38 ms 3192 KB Output is correct
3 Correct 21 ms 2944 KB Output is correct
4 Incorrect 15 ms 2688 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 810 ms 1984 KB Output is correct
2 Correct 90 ms 2936 KB Output is correct
3 Correct 27 ms 2944 KB Output is correct
4 Correct 15 ms 2432 KB Output is correct
5 Correct 186 ms 3200 KB Output is correct
6 Correct 255 ms 3064 KB Output is correct
7 Correct 275 ms 2944 KB Output is correct
8 Correct 18 ms 2688 KB Output is correct
9 Correct 24 ms 2048 KB Output is correct
10 Correct 1100 ms 2348 KB Output is correct
11 Correct 1077 ms 2208 KB Output is correct
12 Correct 1058 ms 2232 KB Output is correct
13 Correct 37 ms 3320 KB Output is correct
14 Correct 49 ms 3060 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 3328 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 8 ms 1792 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -