제출 #1157321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157321		PagodePaiva	장난감 기차 (IOI17_train)	C++20	5 / 100	1201 ms	2408 KiB

train

#include "train.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 5010;
vector <int> g[N];
int n;
int h[N], dp[N], tout[N];
bool on[N], typ[N], mark[N];
vector <int> backedge[N];
vector <int> dfs_tree[N];
vector <int> aux[N];

void dfs(int v, int p){
    mark[v] = 1;
    for(auto x : g[v]){
        if(mark[x] and !tout[x]){
            backedge[v].push_back(x);
            continue;
        }
        else if(mark[x] and tout[x]){
            aux[v].push_back(x);
            continue;
        }
        dfs_tree[v].push_back(x);
        h[x] = h[v]+1;
        dp[x] = dp[v];
        if(on[x]) dp[x] = x;
        dfs(x, v);
    }
    return;
}

int solve[N];

void calc(int v, int p){
    if(typ[v] == 1){
        solve[v] = 0;
        for(auto x : dfs_tree[v]){
            calc(x, v);
            if(solve[x]){
                solve[v] = 1;
                return;
            }
        }
        for(auto x : aux[v]){
            if(solve[x]){
                solve[v] = 1;
                return;
            }
        }
        if(dp[v] == -1) return;
        for(auto x : backedge[v]){
            if(h[x] <= h[dp[v]]){
                solve[v] = 1;
                return;
            }
        }
        return;
    } 
    else{
        solve[v] = 1;
        for(auto x : dfs_tree[v]){
            calc(x, v);
            if(solve[x] == 0){
                solve[v] = 0;
                return;
            }
        }
        for(auto x : aux[v]){
            if(solve[x] == 0){
                solve[v] = 0;
                return;
            }
        }
        for(auto x : backedge[v]){
            if(dp[v] == -1){
                solve[v] = 0;
                return;
            }
            if(h[x] > h[dp[v]]){
                solve[v] = 0;
                return;
            }
        }
        return;
    }
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    for(int i = 0;i < u.size();i++){
        g[u[i]].push_back(v[i]);
    }
    n = a.size();
    for(int i = 0;i < n;i++){
        on[i] = r[i];
        typ[i] = a[i];
    }
    std::vector<int> res;
    for(int raiz = 0;raiz < n;raiz++){
        memset(mark,0, sizeof mark);
        memset(h, 0, sizeof h);
        memset(dp, -1, sizeof dp);
        memset(solve, -1, sizeof solve);
        memset(tout, 0, sizeof tout);
        for(int i = 0;i < n;i++){
            backedge[i].clear();
            dfs_tree[i].clear();
            aux[i].clear();
        }
        if(on[raiz]) dp[raiz] = raiz;
        dfs(raiz, raiz);
        calc(raiz, raiz);
        /*for(int i = 0;i < n;i++){
            cout << i << ": ";
            for(auto x : dfs_tree[i]){
                cout << x << ' ';
            }
            cout << endl;
            for(auto x : aux[i])
                cout << x << ' ';
            cout << endl;
            for(auto x : backedge[i])
                cout << x << ' ';
            cout << endl;
        }*/
        res.push_back(solve[raiz]);
    }
    return res;
}

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