제출 #226957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226957		PedroBigMan	Toy Train (IOI17_train)	C++14	0 / 100	2086 ms	2352 KiB

train

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include "train.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 100000000000000000LL
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}

class DiGraph
{
    public:
    ll N;
    vector<vector<ll> > adj; 
    vector<bool> visited;
    vector<ll> current; //for CC
    vector<bool> c; //for Bip
    bool bip; //for Bip
    vector<ll> TS;//Top Sort
    vector<ll> SCC; //Attributes a number to each node
    vector<vector<ll> > adjK; //reverse graph, for Kosaraju
    
    DiGraph(vector<vector<ll> > ad)
    {
        adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false); c.pb(-1); SCC.pb(-1LL);}
        vector<ll> xx; REP(i,0,N) {adjK.pb(xx);}
        REP(i,0,adj.size())
        {
            REP(j,0,adj[i].size()) {adjK[adj[i][j]].pb(i);}
        }
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
        current.clear();
    }
    
    void DFS(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i]]) {c[adj[s][i]]=(c[s]+1)%2; DFS(adj[s][i]);}
            else if(c[adj[s][i]]==c[s]) {bip=false;}
        }
        current.pb(s); //only needed for Kosaraju
        return;
    }
    
    vector<ll> BFS(ll s) 
    {
        vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
        REP(i,0,N) {visited[i]=false;}
        distance[s]=0; visited[s]=true;
        deque<ll> d; d.pb(s); ll cur;
        while(!d.empty())
        {
            cur=d.front(); d.pop_front();
            REP(i,0,adj[cur].size())
            {
                if(!visited[adj[cur][i]]) 
                {
                    visited[adj[cur][i]]=true; 
                    d.pb(adj[cur][i]); 
                    distance[adj[cur][i]]=distance[cur]+1;
                }
            }
        }
        return distance;
    }
    
    bool Bip()
    {
        c[0]=0; 
        bip=true;
        DFS(0);
        if(bip) {return true;}
        else {return false;}
    }
    
    void DFSTS(ll s)
    {
        REP(i,0,adj[s].size()) 
        {
            if(!visited[adj[s][i]]) {DFSTS(adj[s][i]);}
        }
        visited[s]=true; TS.pb(s);
    }
    
    void TopSort()
    {
        Reset();
        REP(i,0,N)
        {
            if(visited[i]) {continue;}
            DFSTS(i);
        }
        reverse(TS.begin(),TS.end());
    }
    
    void DFSK(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        REP(i,0,adjK[s].size())
        {
            if(!visited[adjK[s][i]]) {DFSK(adjK[s][i]);}
        }
        current.pb(s); //only needed for Kosaraju
        return;
    }
    
    void Kosaraju()
    {
        if(SCC[0]!=-1) {return;}
        Reset();
        REP(i,0,N) 
        {
            if(visited[i]) {continue;}
            DFS(i);
        }
        vector<ll> List=current;
        Reset();
        ll c=0LL;
        for(ll i=N-1LL;i>=0LL;i--)
        {
            ll node=List[i];
            if(visited[node]) {continue;}
            DFSK(node);
            REP(j,0,current.size()) {SCC[current[j]]=c;}
            c++;
            current.clear();
        }
    }
    
    DiGraph SCCGraph()
    {
        Kosaraju();
        set<pl> ed;
        REP(i,0,adj.size())
        {
            REP(j,0,adj[i].size())
            {
                ed.insert(mp(SCC[i],SCC[adj[i][j]]));
            }
        }
        vector<vector<ll> > a; vector<ll> xx;
        ll nscc=-INF; REP(i,0,N) {nscc=max(nscc,SCC[i]+1LL);}
        REP(i,0,nscc) {a.pb(xx);}
        set<pl>::iterator it=ed.begin();
        pl cur;
        while(it!=ed.end())
        {
            cur=*it;
            if(cur.ff!=cur.ss) {a[cur.ff].pb(cur.ss);}
            it++;
        }
        DiGraph ans(a);
        return ans;
    }
};

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) 
{
    ll N=a.size(); ll M=u.size(); 
    vector<vector<ll> > adj; vector<ll> xx; REP(i,0,N) {adj.pb(xx);}
    REP(i,0,M)
    {
        adj[u[i]].pb(v[i]);
    }
    DiGraph G(adj);
	vector<int> ans; REP(i,0,N) {ans.pb(0);}
    REP(s,0,N)
    {
        ll cur=s;
        while(1>0)
        {
            if(find(adj[cur].begin(),adj[cur].end(),cur)==adj[cur].end()) {cur=adj[cur][0];continue;}
            if(r[cur]==1 && a[s]==1) {ans[s]=1; break;} 
            else if(r[cur]==0 && a[s]==0) {break;}
            if(adj[cur].size()==1) {break;}
            cur++;
        }
    }
    return ans;
}

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