제출 #581137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581137		alireza_kaviani	장난감 기차 (IOI17_train)	C++17	0 / 100	2074 ms	1748 KiB

train

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())

const ll MAXN = 5010;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , m , A[MAXN] , R[MAXN] , cnt[MAXN] , ans[MAXN]; 
vector<int> adj[MAXN] , radj[MAXN];

void Solve(){
    queue<int> Q;
    for(int i = 0 ; i < n ; i++){
        if(cnt[i] <= 0){
            Q.push(i);
        }
    }
    while(!Q.empty()){
        int v = Q.front(); Q.pop();
        for(int u : radj[v]){
            cnt[u]--;
            if(cnt[u] == 0){
                Q.push(u);
            }
        }
    }
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    n = SZ(a); m = SZ(u);
    for(int i = 0 ; i < n ; i++){
        A[i] = a[i];
    }
    for(int i = 0 ; i < n ; i++){
        R[i] = r[i];
    }
    for(int i = 0 ; i < m ; i++){
        adj[u[i]].push_back(v[i]);
        radj[v[i]].push_back(u[i]);
    }
    
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            if(i == j){
                cnt[j] = 0;
            }
            else if(A[j]){
                cnt[j] = 1;
            }
            else{
                cnt[j] = SZ(adj[j]);
            }
        }
        Solve();
        cnt[i] = (A[i] ? 1 : SZ(adj[i]));
        for(int j : adj[i]){
            if(i == j || cnt[j] <= 0){
                cnt[i]--;
            }
        }
        for(int j = 0 ; j < n ; j++){
            if(R[j] && cnt[j] <= 0){
                cnt[j] = 0;
            }
            else if(A[j]){
                cnt[j] = 1;
            }
            else{
                cnt[j] = SZ(adj[j]);
            }
        }
        Solve();
        if(cnt[i] <= 0){
            ans[i] = 1;
        }
    }
    for(int i = 0 ; i < n ; i++){
        if(ans[i]){
            cnt[i] = 0;
        }
        else if(A[i]){
            cnt[i] = 1;
        }
        else{
            cnt[i] = SZ(adj[i]);
        }
    }
    Solve();

    vector<int> res;
    for(int i = 0 ; i < n ; i++){
        res.push_back((cnt[i] <= 0 ? 1 : 0));
    }
  	return res;
}

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