Submission #1065808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065808		Faisal_Saqib	Toy Train (IOI17_train)	C++17	100 / 100	1752 ms	2272 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 charge[N],alive[N],vis[N];
sll rem;
ll n,owner[N],m,deg[N],deg_[N];
sll attr(sll& a,ll player)
{
    ll sz=a.size();
    for(auto&i:rem)
    {
        vis[i]=0;
        deg_[i]=deg[i];
    }
    // cout<<"Computing attractor of: ";
    queue<int> q;
    for(auto&i:a)
    {
        // cout<<i<<' ';
        if(alive[i])
        {
            q.push(i);
            vis[i]=1;
        }
    }
    // cout<<endl;
    sll ans;
    // cout<<"reach: ";
    while(q.size())
    {
        int f=q.front();
        q.pop();
        ans.insert(f);
        // cout<<f<<' ';
        for(ll&y:ma[f])
        {
            if(!alive[y])continue;
            deg_[y]--;
            if(owner[y]==player)
            {
                // y have edge to the set a and is own by palyer so he will take the edge
                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;
}
sll attrcomp(sll& a,ll player)
{
    // We never want to reach any vertex in a
    // Reach(a) == compliement( Safety(  compliment( a ) ) ) 
    // Reach( compliment ( a ) ) == compliement( Safety( a ) ) 
    // compliment( Reach( compliment ( a ) ) ) == Safety( a )
    sll cp;
    for(auto&i:a)
        cp.insert(i);
    // if(a.find(i)==a.end())
    cp=attr(cp,player);
    sll ans;
    for(auto&i:rem)
        if(cp.find(i)==cp.end())
            ans.insert(i);
    return ans;
}
sll Buchi(sll& a)
{
    ll sz=a.size();
    while(true)
    {
        auto cur=attrcomp(a,1);
        if(cur.size()==0)break;
        // cout<<"Step\n";
        // cout<<"For a: ";
        // for(auto i:a)
        // {
            // cout<<i<<' ';
        // }
        // cout<<endl;
        // cout<<"Got cur: ";
        // for(auto i:cur)
        // {
            // cout<<i<<' ';
        // }
        // cout<<endl;
        cur=attr(cur,2);
        // cout<<"Got cur: ";
        // for(auto i:cur)
        // {
            // cout<<i<<' ';
        // }
        // cout<<endl;
        for(auto&i:cur){
            auto it=a.find(i);
            if(it!=end(a))
                a.erase(it);                
            auto it1=rem.find(i);
            if(it1!=end(rem))
            {
                for(auto jp:ma[i])
                    deg[jp]--;
                alive[i]=0;
                deg[i]=0;
                ma[i].clear();
                rem.erase(it1);
            }
        }
    }
    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();
    sll vertexs;
    for(int i=1;i<=n;i++)
    {
        rem.insert(i);
        alive[i]=1;
        if(a[i-1]==1)
        {
            owner[i]=1;
        }
        else
        {
            owner[i]=2;
        }
        if(r[i-1])
        {
            vertexs.insert(i);
            charge[i]=1;
        }
        else
        {
            charge[i]=0;
        }
    }
    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]]++;
        // ma[v[j]].pb(u[j]);
    }
    sll answer=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::set<long long int> attr(std::set<long long int>&, long long int)':
train.cpp:16:8: warning: unused variable 'sz' [-Wunused-variable]
   16 |     ll sz=a.size();
      |        ^~
train.cpp: In function 'std::set<long long int> Buchi(std::set<long long int>&)':
train.cpp:87:8: warning: unused variable 'sz' [-Wunused-variable]
   87 |     ll sz=a.size();
      |        ^~

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