Submission #408604

#	Time	Username	Problem	Language	Result	Execution time	Memory
408604		MKopchev	Toy Train (IOI17_train)	C++14	100 / 100	1123 ms	1500 KiB

train

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

const int nmax=5e3+42;
int who[nmax];
int charge[nmax];

vector<int> prv[nmax];

bool on[nmax];
int n;

int outp[nmax];

bool been[nmax];

int owner;

int deg[nmax];

void dfs(int node)
{
    //cout<<"dfs "<<node<<" "<<owner<<endl;

    if(been[node])return;

    been[node]=1;

    for(auto w:prv[node])
    {
        //cout<<"w= "<<w<<" node= "<<node<<endl;

        if(who[w]==owner)dfs(w);
        else
        {
            deg[w]--;
            if(deg[w]==0)dfs(w);
        }
    }
}
vector<int> f(int person,vector<int> start)
{
    for(int i=1;i<=n;i++)been[i]=0;

    owner=person;

    for(auto w:start)
    {
        dfs(w);
    }

    vector<int> ret={};
    for(int i=1;i<=n;i++)
        if(been[i])ret.push_back(i);

    //cout<<"f "<<person<<" start: ";for(auto w:start)cout<<w<<" ";cout<<" ret: ";for(auto w:ret)cout<<w<<" ";cout<<endl;

    return ret;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	n=a.size();
	for(int i=1;i<=n;i++)who[i]=a[i-1];

	for(int i=1;i<=n;i++)charge[i]=r[i-1];

	for(int i=1;i<=n;i++)on[i]=1;

	while(1)
	{
	    for(int i=1;i<=n;i++)
        {
            prv[i]={};
            deg[i]=0;
        }

	    for(int i=0;i<u.size();i++)
        {
            int from=u[i]+1;
            int to=v[i]+1;

            if(on[from]&&on[to])
            {
                prv[to].push_back(from);

                //cout<<"prv "<<to<<" "<<from<<endl;

                deg[from]++;
            }
        }

        vector<int> remain={},charges={};
        for(int i=1;i<=n;i++)
            if(on[i])
            {
                remain.push_back(i);
                if(charge[i])charges.push_back(i);
            }

        vector<int> help=f(1,charges);

        if(help==remain)
        {
            for(auto w:help)
                outp[w]=1;

            break;
        }
        else
        {
            vector<int> other={};

            int j=0;
            for(auto w:remain)
            {
                if(j<help.size()&&w==help[j])j++;
                else other.push_back(w);
            }

            help=f(0,other);

            for(auto w:help)
            {
                on[w]=0;
            }
        }
	}

	vector<int> ret={};
	for(int i=1;i<=n;i++)
        ret.push_back(outp[i]);

    return ret;
}

/*
int main() {
	int n, m;
	assert(2 == scanf("%d %d", &n, &m));

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

	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &a[i]));

	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));

	for(int i = 0; i < m; i++)
		assert(2 == scanf("%d %d", &u[i], &v[i]));

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

	for(int i = 0; i < (int)res.size(); i++)
		printf(i ? " %d" : "%d", res[i]);
	printf("\n");

	return 0;
}
*/

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |      for(int i=0;i<u.size();i++)
      |                  ~^~~~~~~~~
train.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |                 if(j<help.size()&&w==help[j])j++;
      |                    ~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51