Submission #239275

#	Time	Username	Problem	Language	Result	Execution time	Memory
239275		lyc	Toy Train (IOI17_train)	C++14	0 / 100	17 ms	16128 KiB

train

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

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

const int mxN = 2005;
int N, M, A[mxN];
vector<int> al[mxN];
int rf[mxN], src;
int f(int u) {
    if (~rf[u]) return rf[u];
    rf[u] = -2;
    bool tmp = 0;
    for (int v : al[u]) {
        if (v == src) return rf[u] = 1;
        if (rf[v] != -2) tmp |= f(v);
    }
    return rf[u] = tmp;
}
int rg[mxN][mxN];
int g(int u, int p) {
    if (~rg[u][p]) return rg[u][p];
    if (A[u]) {
        rg[u][p] = 0;
        for (int v : al[u]) {
            rg[u][p] |= g(v,p-1);
        }
    } else {
        rg[u][p] = 1;
        for (int v : al[u]) {
            rg[u][p] &= g(v,p-1);
        }
    }
    return rg[u][p];
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    N = SZ(a);
    FOR(i,0,N-1){
        A[i] = a[i];
    }
    M = SZ(u);
    FOR(i,0,M-1){
        al[u[i]].push_back(v[i]);
    }
    memset(rg,-1,sizeof rg);
    FOR(i,0,N-1){
        if (r[i]) {
            src = i;
            memset(rf,-1,sizeof rf);
            f(src);
            FOR(j,0,N-1) if (rf[i] == 1) rg[i][0] = 1;
        }
    }
    FOR(i,0,N-1){
        if (rg[i][0] == 1) {
            FOR(p,0,N-1) rg[i][p] = 1;
        } else {
            rg[i][0] = 0;
        }
    }
	vector<int> res(N);
	for (int i = 0; i < N; i++) {
		res[i] = g(i,N);
    }
	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