oj.uz

Submission #66912

# Submission time Handle Problem Language Result Execution time Memory
66912 2018-08-12T19:00:01 Z yusufake Toy Train (IOI17_train) C++
0 / 100
 23 ms 1972 KB 
#include<bits/stdc++.h>
using namespace std;
 
#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   = 5e3 + 3;
 
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],Q[N],s,z,n,i,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) exit(0);
        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(ans[x] != -1) return;
    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);
      /*  
        for(i=1;i<=z;i++) Q[ Z[i] ] = 1;
        for(i=1;i<=z;i++)
            for(auto y : V[ Z[i] ])
                if(!Q[y])
                    assert(0);
        for(i=1;i<=z;i++) Q[ Z[i] ] = 0;
    */    
        hh = 0;
        for(i=1;i<=z;i++)
            if(R[ Z[i] ] && ans[ Z[i] ] == -1){
                g(Z[i],-1,1);
                hh = 1;
            }
        if(hh) continue;
        for(i=1;i<=z;i++)
            if(ans[ Z[i] ] == -1)
                g(Z[i],-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:41: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:65: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 Incorrect 16 ms 1528 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 3 ms 1528 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1972 KB Output is correct
2 Correct 13 ms 1972 KB Output is correct
3 Correct 17 ms 1972 KB Output is correct
4 Correct 14 ms 1972 KB Output is correct
5 Correct 5 ms 1972 KB Output is correct
6 Correct 12 ms 1972 KB Output is correct
7 Correct 9 ms 1972 KB Output is correct
8 Incorrect 15 ms 1972 KB 3rd lines differ - on the 5th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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