Submission #1100486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100486		azberjibiou	Toy Train (IOI17_train)	C++17	100 / 100	353 ms	2044 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=5005;
const int mxM=2200005;
const int mxK=61;
const int MOD=1e9+7;
const ll INF=1e18;
int N, M;
vector <int> adj[mxN];
vector <int> radj[mxN];
int AB[mxN];
bool imp[mxN];
int cnt;
void input(){
    cin >> N >> M;
    for(int i=0;i<N;i++) cin >> AB[i];
    for(int i=0;i<N;i++) cin >> imp[i];
    for(int i=0;i<M;i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        radj[b].push_back(a);
    }
}
void init(vector <int> a, vector<int> r, vector<int> u, vector<int> v){
    N=a.size(), M=u.size();
    for(int i=0;i<N;i++) AB[i]=a[i];
    for(int i=0;i<N;i++) imp[i]=r[i];
    for(int i=0;i<M;i++){
        int t1=u[i], t2=v[i];
        adj[t1].push_back(t2);
        radj[t2].push_back(t1);
    }
}
bool Chk[mxN];
bool bor[mxN];
int deg[mxN];
queue <int> que;
void solv_reachable(){
    for(int i=0;i<N;i++) deg[i]=adj[i].size(), Chk[i]=false;
    for(int i=0;i<N;i++) if(imp[i]) que.push(i), Chk[i]=true;
    while(que.size()){
        int now=que.front();
        que.pop();
        for(int x : radj[now]) if(!Chk[x]){
            if(AB[x]==1){
                Chk[x]=true;
                que.push(x);
            }
            else{
                deg[x]--;
                if(deg[x]==0){
                    Chk[x]=true;
                    que.push(x);
                }
            }
        }
    }
    for(int i=0;i<N;i++) bor[i]=(!Chk[i]);
}
void destroy_charge(){
    for(int i=0;i<N;i++) deg[i]=adj[i].size(), Chk[i]=false;
    for(int i=0;i<N;i++) if(bor[i]) que.push(i), Chk[i]=true;
    while(que.size()){
        int now=que.front();
        que.pop();
        for(int x : radj[now]) if(!Chk[x]){
            if(AB[x]==0){
                Chk[x]=true;
                que.push(x);
            }
            else{
                deg[x]--;
                if(deg[x]==0){
                    Chk[x]=true;
                    que.push(x);
                }
            }
        }
    }
    for(int i=0;i<N;i++) if(Chk[i]) imp[i]=false;
}
void solv(){
    int pcnt=0;
    for(int i=0;i<N;i++) if(imp[i]) pcnt++;
    while(true){
        solv_reachable();
        destroy_charge();
        int ncnt=0;
        for(int i=0;i<N;i++) if(imp[i]) ncnt++;
        if(pcnt==ncnt) break;
        pcnt=ncnt;
    }
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    init(a, r, u, v);
    solv();
    vector <int> res(N);
    for(int i=0;i<N;i++) res[i]=(bor[i] ? 0 : 1);
    return res;
}
/*
int main(){
    input();
    solv();
    for(int i=0;i<N;i++) cout << (bor[i] ? 0 : 1) << " ";
}
*/

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