Submission #408310

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
408310	2021-05-19T06:55:39 Z	balbit	Toy Train (IOI17_train)	C++14	0 / 100	2000 ms	2028 KB

train

#include "train.h"

#include <bits/stdc++.h>
using namespace std;
//#define BALBIT
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 5e3+5;

bool win[maxn];
int safe[maxn]; // safe edges coming out of this node

vector<int> g[maxn];
bool notcyc[maxn];
vector<int> rg[maxn];

std::vector<int> win2(std::vector<int> who, std::vector<int> station, std::vector<int> UU, std::vector<int> VV) {
	int n = SZ(who);
	std::vector<int> res(n);
	REP(i,n) g[i].clear(), rg[i].clear();
	memset(win, 0, sizeof win);
	memset(safe, 0, sizeof safe);
	memset(notcyc, 0, sizeof notcyc);
    REP(i,SZ(UU)) {
        g[UU[i]].pb(VV[i]);
        rg[VV[i]].pb(UU[i]);
    }
//    return res;
    REP(round, 3)
    REP(T, n) {
        if (res[T]) continue;
        // T is target node
        if (!station[T]) continue;
        // who = 1: any is required to win
        REP(i,n) safe[i] = SZ(g[i]);
        memset(win, 0, sizeof win);
        win[T] = 1;
        queue<int> q;
        REP(i,n) if (res[i] || i==T) q.push(i);
        while (!q.empty() ){
            int v = q.front(); q.pop();
            for (int u : rg[v]) {
                if (!win[u]) {
                    if (who[u] == 1) {
                        // any required
//                        bug(u, who[u]);
                        win[u] = 1; q.push(u);
                    }else{
                        -- safe[u];
                        if (safe[u] == 0) {
                            q.push(u);
                            win[u] = 1;
                        }
                    }
                }
            }
        }
//        continue;
        bool ok = 0;
        if (who[T] == 1) {
            // any required
            for (int u : g[T]) {
                if (win[u]) {
                    ok = 1; break;
                }
            }
        }else{
            ok = 1;
            for (int u : g[T]) {
                if (!win[u]) {
//                    bug(T, u, win[u]);
                    ok=0; break;
                }
            }
        }
//        bug(T, ok);
        if (ok) {
            REP(i,n) {
//                bug(i, win[i]);
                if (win[i]) res[i] = 1;
            }
        }
    }
	return res;
}

//bitset<maxn> fren[maxn];
vector<int> love[maxn];
int nlove[maxn];
int seff[maxn][2];
bool touch[maxn][2];

std::vector<int> who_wins(std::vector<int> who, std::vector<int> station, std::vector<int> UU, std::vector<int> VV) {
	int n = SZ(who);
	std::vector<int> res(n);
	REP(i,n) g[i].clear(), rg[i].clear();
	memset(win, 0, sizeof win);
	memset(safe, 0, sizeof safe);
	memset(notcyc, 0, sizeof notcyc);
	memset(nlove, 0, sizeof nlove);
    REP(i,n) love[i].clear();
    REP(i,SZ(UU)) {
        g[UU[i]].pb(VV[i]);
        rg[VV[i]].pb(UU[i]);
    }
//    return res;
    {

        queue<int> q;
        REP(i,n) {
            if (station[i]) q.push(i), notcyc[i] = 1;
            else safe[i] = SZ(g[i]);
        }
        // create things that aren't zero-cycles
        while (!q.empty() ) {
            int v = q.front(); q.pop();
            for (int u : rg[v]) {
                if (!notcyc[u]) {
                    if (who[u] == 1) {
                        // i like stations!
                        notcyc[u] = 1; q.push(u);
                    }else{
                        --safe[u];
                        if( safe[u] == 0) {
                            notcyc[u] = 1; q.push(u);
                        }
                    }
                }
            }
        }
    }
     REP(T, n) {
        if (res[T]) continue;
        // T is target node
        if(!(station[T] || (notcyc[T]))) {
            continue;
        }
        bug(T);
        // who = 1: any is required to win
        REP(i,n) seff[i][0] = seff[i][1] = SZ(g[i]);
        memset(touch, 0, sizeof touch);
        touch[T][station[T]] = 1;
        vector<pii> q; q.pb({T, station[T]});
        int IT = 0;
        while (IT < SZ(q)){
            int v = q[IT].f; bool B = q[IT].s; ++IT;
            if (!touch[v][0]) {
                touch[v][0] = 1; q.pb({v,0});
            }
            for (int u : rg[v]) {
                bool he = B | station[u];
                if (!touch[u][he]) {
                    if (who[u] == 1) {
                        // any required
//                        bug(u, who[u]);
                        touch[u][he] = 1; q.pb({u,he});
                    }else{
//                        -- seff[u][he];
                        if (--seff[u][he] == 0) {
                            q.pb({u,he});
                            touch[u][he] = 1;
                        }
                    }
                }
            }
        }
        bool ok = 0;
        if (who[T] == 1) {
            // any required
            for (int u : g[T]) {
                if (touch[u][1]) {
                    ok = 1; break;
                }
            }
        }else{
            ok = 1;
            for (int u : g[T]) {
                if (!touch[u][1]) {
//                    bug(T, u, win[u]);
                    ok=0; break;
                }
            }
        }
        bug(T, ok);
        touch[T][1] = ok;
        if (ok)
            res[T] = 1;

    }
    return res;

    memset(win, 0, sizeof win);
    {
        queue<int> q;
        REP(i,n) {
            if (!notcyc[i] || (who[i] == 1 && nlove[i] == 0)) {
                bug(i, notcyc[i]);
                q.push(i);
                win[i] = 1;
            }
//            safe[i] = SZ(g[i]);
        }
        bitset<maxn> alive;
        alive.set();
        while (!q.empty() ) {
            int v = q.front(); q.pop();
//            if (win[v]) continue;
            for (int u : rg[v]) {
                if (!win[u]) {
                    if (who[u] == 0) {
                        // i hate stations!
                        win[u] = 1; q.push(u);
                    }
                }
            }
            if (station[v]) {
                for (int u : love[v]) {
                    if (!win[u])
                        if (who[u] == 1 && (--nlove[u] <= 0) ) {
                            q.push(u); win[u] = 1;
                        }
                }
            }
        }

    }
    REP(i,n) res[i] = !win[i];
	return res;
}
#ifdef BALBIT
signed main() {
    int n,m; cin>>n>>m;
    REP(ffff, 1000) {
        vector<int >a,r;
        REP(i,n) a.pb(rand()%2);
        REP(i,n) {
            r.pb(rand()%2);
            if (r.back()) a[i] = 1;
        }
        vector<int> u,v;
        REP(i,m) {
            u.pb(rand()%n);
            if (i<n) u[i] = i;
            v.pb(rand()%n);
        }
        vector<int> r1 = win2(a,r,u,v);
        vector<int> r2 = who_wins(a,r,u,v);
        if (r1 != r2) {
            for (int x : r1) cout<<x<<' ';
            cout<<endl;
            for (int x : r2) cout<<x<<' ';
            cout<<endl;

            cout<<"A"<<endl;
            for (int x : a) cout<<x<<' ';
            cout<<endl;
            for (int x : r) cout<<x<<' ';
            cout<<endl;
            for (int x : u) cout<<x<<' ';
            cout<<endl;
            for (int x : v) cout<<x<<' ';
            cout<<endl;
            assert(0);
        }
    }
}
#endif
/*
2 4
0 1
1 0
0 0
0 1
1 0
1 1

*/

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	37 ms	1228 KB	3rd lines differ - on the 14th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	716 KB	3rd lines differ - on the 4th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	913 ms	2028 KB	Output is correct
2	Correct	945 ms	1836 KB	Output is correct
3	Correct	1226 ms	1828 KB	Output is correct
4	Execution timed out	2086 ms	1800 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-