Submission #1065832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065832		Faisal_Saqib	Toy Train (IOI17_train)	C++17	0 / 100	5 ms	1520 KiB

train

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

#define ll long long
#define vll vector<ll>
#define pb push_back
#define sll set<ll>

const int N=5e3+10;
vll ma[N];
bool alive[N],vis[N],lcp[N];
ll n,owner[N],m,deg[N],deg_[N];
vll attr(vll&a,ll player)
{
    ll sz=a.size();
    for(int i=1;i<=n;i++)
        if(alive[i])
        {
            vis[i]=0;
            deg_[i]=deg[i];
        }
    queue<int> q;
    for(auto&i:a)
        if(alive[i])
        {
            q.push(i);
            vis[i]=1;
        }
    vll ans;
    while(q.size())
    {
        int f=q.front();
        q.pop();
        ans.push_back(f);
        for(ll&y:ma[f])
        {
            if(!alive[y])continue;
            deg_[y]--;
            if(owner[y]==player)
            {
                if(!vis[y])
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
            else // Owned by other player
            {
                if(deg_[y]==0 and vis[y]==0)
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
    // cout<<endl;
    return ans;
}
vll Buchi(vll a)
{
    ll sz=a.size();
    while(true)
    {
        auto cur=attr(a,1);
        for(int i=1;i<=n;i++)lcp[i]=0;
        for(auto&i:cur)lcp[i]=1;
        cur.clear();
        for(int i=1;i<=n;i++)
            if(alive[i])
                cur.push_back(i);
        if(cur.size()==0)break;
        cur=attr(cur,2);
        for(auto&i:cur){
            for(auto jp:ma[i])
                deg[jp]--;
            alive[i]=0;
            deg[i]=0;
            ma[i].clear();
        }
    }
    return a;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v)
{
    n=a.size();
    vll vertexs;
    for(int i=1;i<=n;i++)
    {
        alive[i]=1;
        if(a[i-1]==1)
            owner[i]=1;
        else
            owner[i]=2;
        if(r[i-1])
            vertexs.push_back(i);
    }
    m=u.size();
    for(int j=0;j<m;j++)
    {
        u[j]++;
        v[j]++;
        ma[v[j]].pb(u[j]); // Directed edges
        deg[u[j]]++;
    }
    Buchi(vertexs);
    vector<int> ap(n);
    for(int i=1;i<=n;i++)
        ap[i-1]=alive[i];
    return ap;
}

Compilation message (stderr)

train.cpp: In function 'std::vector<long long int> attr(std::vector<long long int>&, long long int)':
train.cpp:15:8: warning: unused variable 'sz' [-Wunused-variable]
   15 |     ll sz=a.size();
      |        ^~
train.cpp: In function 'std::vector<long long int> Buchi(std::vector<long long int>)':
train.cpp:62:8: warning: unused variable 'sz' [-Wunused-variable]
   62 |     ll sz=a.size();
      |        ^~

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