제출 #1218815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218815		mariza	장난감 기차 (IOI17_train)	C++20	0 / 100	2095 ms	1908 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;

    vector<pair<bool,ll>> z;
    for(auto nxt:g[curr]){
        z.push_back({!vis[nxt]&&nxt!=curr,nxt});
    }
    sort(z.begin(),z.end());

    bool ans;
    if(o[curr]==1){
        x[curr]=0;
        for(auto nxt:z){
            x[curr]|=dfs(nxt.second);
        }
        ans=x[curr];
    }
    else{
        ans=1;
        for(auto nxt:z){
            ans&=dfs(nxt.second);
        }
    }
    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];
        g[i].clear();
    }
    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