Submission #548131

#	Time	Username	Problem	Language	Result	Execution time	Memory
548131		lucaperju	Toy Train (IOI17_train)	C++17	100 / 100	289 ms	1712 KiB

train

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

vector<int>ed[5005];
vector<int>in[5005];
int cnt[5005],inq[5005];
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	std::vector<int> res(a.size());
    for(int i=0;i<u.size();++i)
    {
        ed[u[i]].push_back(v[i]);
        in[v[i]].push_back(u[i]);
    }
    while(1)
    {
        vector<int> S(a.size());
        vector<int> toProcess;
        int i,n=a.size();
        for(i=0;i<n;++i)
            inq[i]=cnt[i]=0;
        for(i=0;i<n;++i)
            if(r[i])
                S[i]=1;
            else
                S[i]=0;
        for(i=0;i<n;++i)
        {
            if(S[i])
            {
                for(int j=0;j<in[i].size();++j)
                {
                    int x=in[i][j];
                    if(!S[x] && !inq[x])
                    {
                        ++cnt[x];
                        if(cnt[x]>0 && a[x]==1 || cnt[x]==ed[x].size() && a[x]==0)
                        {
                            inq[x]=1;
                            toProcess.push_back(x);
                        }
                    }
                }
            }
        }
        while(!toProcess.empty())
        {
            int i=toProcess.back();
            toProcess.pop_back();
            inq[i]=0;
            S[i]=1;
            for(int j=0;j<in[i].size();++j)
            {
                int x=in[i][j];
                if(!S[x] && !inq[x])
                {
                    ++cnt[x];
                    if(cnt[x]>0 && a[x]==1 || cnt[x]==ed[x].size() && a[x]==0)
                    {
                        inq[x]=1;
                        toProcess.push_back(x);
                    }
                }
            }
        }
        int pz=-1;
        for(i=0;i<n;++i)
        {
            if(r[i]==1)
            {
                int cntc=0;
                for(int j=0;j<ed[i].size();++j)
                    if(!S[ed[i][j]])
                        ++cntc;
                if(a[i]==0 && cntc>0 || a[i]==1 && cntc==ed[i].size())
                {
                    pz=i;
                    break;
                }
            }
        }
        if(pz==-1)
            return S;
        r[pz]=0;
    }
}

/*
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:10:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i=0;i<u.size();++i)
      |                 ~^~~~~~~~~
train.cpp:31:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 for(int j=0;j<in[i].size();++j)
      |                             ~^~~~~~~~~~~~~
train.cpp:37:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                         if(cnt[x]>0 && a[x]==1 || cnt[x]==ed[x].size() && a[x]==0)
      |                                                   ~~~~~~^~~~~~~~~~~~~~
train.cpp:37:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |                         if(cnt[x]>0 && a[x]==1 || cnt[x]==ed[x].size() && a[x]==0)
      |                            ~~~~~~~~~^~~~~~~~~~
train.cpp:52:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for(int j=0;j<in[i].size();++j)
      |                         ~^~~~~~~~~~~~~
train.cpp:58:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                     if(cnt[x]>0 && a[x]==1 || cnt[x]==ed[x].size() && a[x]==0)
      |                                               ~~~~~~^~~~~~~~~~~~~~
train.cpp:58:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |                     if(cnt[x]>0 && a[x]==1 || cnt[x]==ed[x].size() && a[x]==0)
      |                        ~~~~~~~~~^~~~~~~~~~
train.cpp:72:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |                 for(int j=0;j<ed[i].size();++j)
      |                             ~^~~~~~~~~~~~~
train.cpp:75:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 if(a[i]==0 && cntc>0 || a[i]==1 && cntc==ed[i].size())
      |                                                    ~~~~^~~~~~~~~~~~~~
train.cpp:75:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   75 |                 if(a[i]==0 && cntc>0 || a[i]==1 && cntc==ed[i].size())

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