oj.uz

Submission #66616

# Submission time Handle Problem Language Result Execution time Memory
66616 2018-08-11T19:10:28 Z yusufake Toy Train (IOI17_train) C++
0 / 100
 2000 ms 2928 KB 
#include<bits/stdc++.h>
using namespace std;

#define _   int v, int tl, int tr, int l, int r, pp x
#define tm  (tl + tr >> 1)
#define sol v,tl,tm,l,r,x
#define sag v,tm+1,tr,l,r,x

#define mp make_pair
#define pb push_back
#define st first
#define nd second

typedef long long ll;
typedef pair < int , int > pp;
typedef vector < int > vi;

const int mod = 1e9 + 7;
const int N   = 1e4 + 4;

vector < int > V[N],Y[N],iyi,kot; 
int H[N],D[N],low[N],T,S[N],Z[N],own[N],R[N],ans[N],s,z,n,i,x,y,t,hh;

void f(int x){
    if(z) return;
    H[x] = D[x] = low[x] = ++T;
    S[++s] = x;
    for(auto y : V[x]){
        if(z) return;
        if(ans[y] != -1) continue;
        if(!D[y]){
            f(y); low[x] = min(low[x] , low[y]);
        }
        else if(H[y]) low[x] = min(low[x] , D[y]);
    }    
    if(low[x] == D[x]){
        for(int y=-1; y!=x;){
            y = S[s--];
            Z[++z] = y;
            H[y] = 0;
        }
    }
}

void del(int x, int y){
    for(int i=0; i<V[x].size(); i++)
        if(V[x][i] == y){
            V[x].erase(V[x].begin() + i);
            return;
        }
}

void g(int x, int p, int h){
    if(p != -1 && own[x] != h){
        if(V[x].size() > 1){
            del(x,p);
            return;
        }
    } 
    ans[x] = h; t--;
    for(auto y : Y[x]) if(ans[y] == -1) g(y,x,h);
}

vi who_wins(vi a, vi r, vi u, vi v){
    t = n = a.size();
    for(i=0;i<n;i++) R[i] = r[i];
    for(i=0;i<n;i++) own[i] = a[i];
    memset(ans,-1,sizeof ans);
    for(i=0;i<u.size();i++){
        V[ u[i] ].pb(v[i]);
        Y[ v[i] ].pb(u[i]);
    }
    
    for(; t ;){
        memset(D,0,sizeof D);
        memset(low,0,sizeof low);
        memset(H,0,sizeof H);
        z = s = 0;
        for(i=0;i<n;i++)
            if(!D[i] && ans[i] == -1) f(i);
        //cout << t << " " << z << " aa\n";
        hh = 0;
        for(i=1;i<=z;i++)
            if(R[ Z[i] ]){
                ans[ Z[i] ] = 1;
                g(x,-1,1);
                break;
            }
        if(i <= z) continue;
        for(i=1;i<=z;i++){
            ans[ Z[i] ] = 0;
            g(x,-1,0);
        }
    }    
    vector < int > vv;
    for(i=0;i<n;i++){
        //cout << ans[i] << " ";
        vv.pb(ans[i]);
    }
    return vv;
}        
/*
int main(){
    who_wins({0, 1}, {1, 0}, {0, 0, 1, 1}, {0, 1, 0, 1});
    return 0;
}
*/

Compilation message

train.cpp: In function 'void del(int, int)':
train.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<V[x].size(); i++)
                  ~^~~~~~~~~~~~
train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:69:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<u.size();i++){
             ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 1880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 2420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 2420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 2928 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 Execution timed out 2055 ms 1880 KB Time limit exceeded
2 Halted 0 ms 0 KB -