제출 #1218787

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

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=5000;

vector<ll> g[N];
bool o[N];

bool x[N];
bool vis[N]={};
bool dfs(ll curr){
    // cout<<curr<<endl;
    if(vis[curr]) return x[curr];
    vis[curr]=1;
    
    bool ans;
    if(o[curr]==1){
        ans=0;
        for(auto nxt:g[curr]){
            ans|=dfs(nxt);
        }
    }
    else{
        ans=1;
        for(auto nxt:g[curr]){
            ans&=dfs(nxt);
        }
    }
    return x[curr]=ans;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    ll n=a.size(), m=u.size();
    for(ll i=0; i<n; i++){
        o[i]=a[i];
    }
    for(ll i=0; i<m; i++){
        g[u[i]].push_back(v[i]);
    }

    vector<int> ans(n,0);
    for(ll i=0; i<n; i++){
        // cout<<"---"<<i<<"---"<<endl;
        if(!r[i]) continue;

        for(ll j=0; j<n; j++){
            x[j]=0;
            vis[j]=0;
        }

        x[i]=1;
        dfs(i);

        for(ll j=0; j<n; j++){
            vis[j]=0;
        }
        vis[i]=1;
        for(ll j=0; j<n; j++){
            if(!vis[j]) dfs(j);
        }

        for(ll j=0; j<n; j++){
            ans[j]|=x[j];
            // cout<<x[j]<<" ";
        }
        // cout<<endl;
    }
    return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51