Submission #932081

#	Time	Username	Problem	Language	Result	Execution time	Memory
932081		ainta	Toy Train (IOI17_train)	C++17	100 / 100	899 ms	2140 KiB

train

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

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
#define N_ 5010
int n, m, removed[N_], attr[N_], Q[N_], Deg[N_];
vi E[N_], F[N_];

auto Attr(vi T, int ck, vi &a, vi &r, vi &vis){
    int head=0,tail=0;
    rep(i,n)vis[i]=Deg[i]=0;
    auto QAdd = [&](int x){
        if(!removed[x] && !vis[x])Q[++tail] = x, vis[x]=1;
    };
    rep(i,n){
        if(removed[i])continue;
        if(T[i]){
            QAdd(i);
        }
        for(auto &x: F[i]){
            if(removed[x])continue;
            if(a[x] != ck)Deg[x]++;
        }
    }
    rep(i,n){
        if(removed[i])continue;
        if(a[i] != ck && !Deg[i])QAdd(i);
    }
    while(head < tail){
        int x = Q[++head];
        for(auto &y : F[x]){
            if(removed[y])continue;
            if(a[y] == ck)QAdd(y);
            if(a[y] != ck){
                Deg[y]--;
                if(!Deg[y])QAdd(y);
            }
        }
    }
}
extern std::vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = a.size();
	m = u.size();
	int i, j, k;
    vi res(n), T(n);
    rep(i,m){
        E[u[i]].pb(v[i]);
        F[v[i]].pb(u[i]);
    }
    vi Attr0(n), Attr1(n);
    while(1){
        rep(i,n){
            T[i]=0;
            if(removed[i])continue;
            if(r[i])T[i]=1;
        }
        Attr(T, 1, a, r, Attr1);
        rep(i,n)if(!removed[i]) Attr1[i] = !Attr1[i];
        Attr(Attr1, 0, a, r, Attr0);
        int ck=0;
        rep(i,n){
            if(!removed[i] && Attr0[i])removed[i]=1, ck=1;
        }
        if(!ck)break;
    }
    rep(i,n)res[i] = !removed[i];
	return res;
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:66:6: warning: unused variable 'i' [-Wunused-variable]
   66 |  int i, j, k;
      |      ^
train.cpp:66:9: warning: unused variable 'j' [-Wunused-variable]
   66 |  int i, j, k;
      |         ^
train.cpp:66:12: warning: unused variable 'k' [-Wunused-variable]
   66 |  int i, j, k;
      |            ^

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