제출 #66910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66910		yusufake	Toy Train (IOI17_train)	C++98	0 / 100	20 ms	3184 KiB

train

#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) 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);
      /*  
        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;  }

컴파일 시 표준 에러 (stderr) 메시지

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:64: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