Submission #66616

#	Time	Username	Problem	Language	Result	Execution time	Memory
66616		yusufake	Toy Train (IOI17_train)	C++98	0 / 100	2081 ms	2928 KiB

train

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51