Submission #283134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
283134	2020-08-25T10:24:56 Z	MKopchev	Toy Train (IOI17_train)	C++14	11 / 100	23 ms	10744 KB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+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;
}
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++)
    {
        adj[u[i]].push_back(v[i]);
        trav[v[i]].push_back(u[i]);

        edges.insert({u[i],v[i]});
    }
    //A 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]})))
        {
            for(auto k:seen)
                charge_comp[pointer]=charge_comp[pointer]|charge[k];
        }

        //cout<<pointer<<" -> "<<charge_comp[pointer]<<endl;
    }

    for(int i=0;i<u.size();i++)
        if(comp[u[i]]!=comp[v[i]])
        {
            //cout<<"adj_comp "<<comp[u[i]]<<" "<<comp[v[i]]<<endl;
            adj_comp[comp[u[i]]].push_back(comp[v[i]]);
        }

    vector<int> outp={};

    for(int i=0;i<n;i++)
        outp.push_back(win(comp[i]));
    /*
    for(int i=0;i<n;i++)
    {
        cout<<outp[i]<<" "<<rec(i)<<endl;
    }
    */

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	10616 KB	Output is correct
2	Correct	21 ms	10744 KB	Output is correct
3	Correct	20 ms	10624 KB	Output is correct
4	Correct	23 ms	10624 KB	Output is correct
5	Correct	23 ms	10488 KB	Output is correct
6	Correct	23 ms	10496 KB	Output is correct
7	Correct	22 ms	10368 KB	Output is correct
8	Correct	22 ms	10488 KB	Output is correct
9	Correct	21 ms	10368 KB	Output is correct
10	Correct	21 ms	10368 KB	Output is correct
11	Correct	21 ms	10368 KB	Output is correct
12	Correct	21 ms	10240 KB	Output is correct
13	Correct	22 ms	10616 KB	Output is correct
14	Correct	23 ms	10616 KB	Output is correct
15	Correct	23 ms	10624 KB	Output is correct
16	Correct	22 ms	10492 KB	Output is correct
17	Correct	22 ms	10496 KB	Output is correct
18	Correct	16 ms	9856 KB	Output is correct