Submission #921954

#	Time	Username	Problem	Language	Result	Execution time	Memory
921954		HuyQuang_re_Zero	Toy Train (IOI17_train)	C++14	11 / 100	261 ms	9700 KiB

train

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
using namespace std;
#include "train.h"
int d[5005],own[N],is_charge[N],U[N],V[N],n,m,i,u,v,res[N],deg[5005];
vector <int> a[N];
vector <int> who_wins(vector <int> _own,vector <int> _is_charge,vector <int> _U,vector <int> _V)
{
    for(i=0;i<_own.size();i++)
    {
        n++;
        own[n]=_own[i]; is_charge[n]=_is_charge[i];
    }
    for(i=0;i<_U.size();i++)
    {
        m++;
        U[m]=_U[i]+1; V[m]=_V[i]+1;
    }

    memset(res,-1,sizeof(res));
    while(1)
    {
        for(u=1;u<=n;u++) a[u].clear();
        memset(deg,0,sizeof(deg));
        for(i=1;i<=m;i++)
        {
            u=U[i]; v=V[i];
            if(res[u]==-1 && res[v]==-1)
                a[v].push_back(u),deg[u]++;
        }
        auto BFS=[&](vector <int> vec,int ok)
        {
            memset(d,0,sizeof(d));
            queue <int> q;
            for(int u:vec) q.push(u),d[u]=1;
            while(q.size()>0)
            {
                int u=q.front(); q.pop();
                for(int v:a[u])
                {
                    deg[v]--;
                    if(d[v]==0 && (deg[v]==0 || own[v]==ok))
                        q.push(v),d[v]=1;
                }
            }
        };
        vector <int> vec;
        for(u=1;u<=n;u++)
            if(res[u]==-1 && is_charge[u])
                vec.push_back(u);
        BFS(vec,1);
        vec.clear();
        for(u=1;u<=n;u++)
            if(res[u]==-1 && d[u]==0)
                vec.push_back(u);
        if(vec.size()==0)
        {
            for(u=1;u<=n;u++)
                if(res[u]==-1) res[u]=1;
            break;
        }
        BFS(vec,0);
        for(u=1;u<=n;u++)
            if(res[u]==-1 && d[u]==1)
                res[u]=0;
    }
    vector <int> w;
    for(u=1;u<=n;u++) w.push_back(res[u]);
    return w;
}
/*
int main()
{
    freopen("train.inp","r",stdin);
    freopen("train.out","w",stdout);
    int n,m,k; cin>>n>>m;
    vector <int> own,is_charge,U,V;
    for(int i=1;i<=n;i++) cin>>k,own.push_back(k);
    for(int i=1;i<=n;i++) cin>>k,is_charge.push_back(k);
    for(int i=1;i<=m;i++) cin>>u,U.push_back(u);
    for(int i=1;i<=m;i++) cin>>v,V.push_back(v);
    vector <int> w=who_wins(own,is_charge,U,V);
    for(int k:w) cout<<k<<" ";
}

*/

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:24:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(i=0;i<_own.size();i++)
      |             ~^~~~~~~~~~~~
train.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(i=0;i<_U.size();i++)
      |             ~^~~~~~~~~~

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