Submission #581137

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
581137	2022-06-22T09:33:07 Z	alireza_kaviani	Toy Train (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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-