oj.uz

답안 #660968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660968 2022-11-23T18:31:20 Z urosk 장난감 기차 (IOI17_train) C++14
11 / 100
 836 ms 1384 KB 
#include "train.h"
#define dbg(x) cerr<<#x<<": "<<x<<endl
#define here cerr<<"===================================\n"
#include <bits/stdc++.h>
#define ll int
#define sz(a) (ll)(a.size())
#define pb push_back
#define popb pop_back
#define all(a) a.begin(),a.end()
#define llinf 1000000000LL
#define fi first
#define sc second
#define pll pair<ll,ll>
#define endl '\n'
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 5005
ll n,m,it;
vector<ll> ans;
vector<ll> g[maxn];
vector<ll> cur;
bool c[maxn];
bool vis[maxn];
bool naso = 0;
bool ok[maxn];
ll cnt = 0;
ll in[maxn],out[maxn];
void dfs(ll u,ll poc){
    vis[u] = 1;
    for(ll s : g[u]){
        if(c[s]) continue;
        if(s==poc){
            naso = 1;
            return;
        }
        if(vis[s]) continue;
        dfs(s,poc);
        if(naso) return;
    }
}
void dfs2(ll u,ll poc){
    if(c[u]) cnt++;
    vis[u] = 1;
    for(ll s : g[u]){
        if(s==poc&&(cnt>0)){
            naso = 1;
            return;
        }
        if(vis[s]) continue;
        dfs(s,poc);
        if(naso) return;
    }
    if(c[u]) cnt--;
}
void dfs3(ll u){
    vis[u] = 1;
    for(ll s : g[u]){
        if(vis[s]) continue;
        dfs3(s);
        ok[u]|=ok[s];
    }
}
vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v) {
    reverse(all(u)); u.pb(-1); reverse(all(u));
    reverse(all(v)); v.pb(-1); reverse(all(v));
    reverse(all(r)); r.pb(-1); reverse(all(r));
    ll sum = 0; for(ll x : a) sum+=x;
    n = sz(a);
    m = sz(u)-1;
    for(ll i = 1;i<=n;i++) c[i] = r[i];
    for(ll i = 1;i<=m;i++){
        u[i]++; v[i]++;
        ll x = u[i]; ll y = v[i];
        g[x].pb(y);
    }
    if(sum==0){
        for(ll i = 1;i<=n;i++){
            if(c[i]) continue;
            for(ll j = 1;j<=n;j++) vis[j] = 0;
            naso = 0;
            dfs(i,i);
            if(naso) ok[i] = 1;
        }
        for(ll i = 1;i<=n;i++){
            for(ll j = 1;j<=n;j++) vis[j] = 0;
            dfs3(i);
        }
        for(ll i = 1;i<=n;i++) ans.pb(1^ok[i]);
        return ans;
    }
    if(sum==n){
        for(ll i = 1;i<=n;i++){
            for(ll j = 1;j<=n;j++) vis[j] = 0;
            naso = 0;
            cnt = 0;
            dfs2(i,i);
            if(naso) ok[i] = 1;
        }
        for(ll i = 1;i<=n;i++){
            for(ll j = 1;j<=n;j++) vis[j] = 0;
            dfs3(i);
        }
        for(ll i = 1;i<=n;i++) ans.pb(1^ok[i]);
        return ans;
    }
	return {};
}

/*
4 6
0 0 0 0
0 1 0 0
0 1
0 2
0 3
1 2
1 3
2 3
*/

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 724 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 209 ms 1384 KB 3rd lines differ - on the 553rd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 649 ms 1056 KB Output is correct
2 Correct 186 ms 988 KB Output is correct
3 Correct 366 ms 1188 KB Output is correct
4 Correct 363 ms 1060 KB Output is correct
5 Correct 500 ms 1188 KB Output is correct
6 Correct 424 ms 1060 KB Output is correct
7 Correct 446 ms 1160 KB Output is correct
8 Correct 322 ms 980 KB Output is correct
9 Correct 23 ms 932 KB Output is correct
10 Correct 806 ms 1272 KB Output is correct
11 Correct 808 ms 1272 KB Output is correct
12 Correct 836 ms 1260 KB Output is correct
13 Correct 663 ms 1264 KB Output is correct
14 Correct 391 ms 1028 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 980 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 724 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -