답안 #581137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581137	2022-06-22T09:33:07 Z	alireza_kaviani	장난감 기차 (IOI17_train)	C++17	0 / 100	2000 ms	1748 KB

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.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	361 ms	1100 KB	3rd lines differ - on the 26th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	468 KB	3rd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	772 ms	1452 KB	Output is correct
2	Correct	870 ms	1484 KB	Output is correct
3	Correct	1014 ms	1436 KB	Output is correct
4	Correct	1957 ms	1420 KB	Output is correct
5	Correct	1473 ms	1416 KB	Output is correct
6	Correct	1012 ms	1416 KB	Output is correct
7	Correct	1236 ms	1404 KB	Output is correct
8	Correct	587 ms	1528 KB	Output is correct
9	Correct	483 ms	1488 KB	Output is correct
10	Correct	769 ms	1380 KB	Output is correct
11	Correct	618 ms	1364 KB	Output is correct
12	Correct	218 ms	1324 KB	Output is correct
13	Execution timed out	2072 ms	1524 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-