oj.uz

Submission #921947

# Submission time Handle Problem Language Result Execution time Memory
921947 2024-02-04T14:59:21 Z HuyQuang_re_Zero Toy Train (IOI17_train) C++14
11 / 100
 266 ms 9688 KB 
#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)
    {
        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++) 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]++;
        }
        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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9064 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 2 ms 8796 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 93 ms 9564 KB Output is correct
2 Correct 199 ms 9560 KB Output is correct
3 Correct 266 ms 9680 KB Output is correct
4 Incorrect 9 ms 9564 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 6 ms 9564 KB Output is correct
2 Correct 6 ms 9604 KB Output is correct
3 Correct 7 ms 9564 KB Output is correct
4 Correct 7 ms 9612 KB Output is correct
5 Correct 7 ms 9688 KB Output is correct
6 Correct 8 ms 9564 KB Output is correct
7 Correct 7 ms 9592 KB Output is correct
8 Correct 7 ms 9564 KB Output is correct
9 Correct 6 ms 9564 KB Output is correct
10 Correct 7 ms 9600 KB Output is correct
11 Correct 7 ms 9564 KB Output is correct
12 Correct 9 ms 9564 KB Output is correct
13 Correct 7 ms 9484 KB Output is correct
14 Correct 8 ms 9600 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9560 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 6 ms 9064 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -