oj.uz

답안 #660982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660982 2022-11-23T18:58:22 Z urosk 장난감 기차 (IOI17_train) C++14
22 / 100
 1800 ms 1604 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;
ll b[maxn];
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;
        dfs2(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];
    }
}
bool dfs4(ll u){
    bool tu = 0;
    for(ll s : g[u]) if(s==u) tu = 1;
    if(!tu){
        return dfs4(g[u][0]);
    }
    if(!b[u]&&!c[u]) return 0;
    if(b[u]&&c[u]) return 1;
    for(ll s : g[u]){
        if(s!=u) return dfs4(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);
    reverse(all(a)); a.pb(-1); reverse(all(a));
    for(ll i = 1;i<=n;i++) b[i] = a[i];
    m = sz(u)-1;
    bool sub1 = 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);
        sub1&=((x==y)||(y-x==1));
    }
    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(ok[i]);
        return ans;
    }
    if(sub1){
        for(ll i = 1;i<=n;i++){
            for(ll j = 1;j<=n;j++) vis[j] = 0;
            ok[i] = dfs4(i);
        }
        for(ll i = 1;i<=n;i++) ans.pb(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
*/

Compilation message

train.cpp: In function 'bool dfs4(int)':
train.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
   75 | }
      | ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 1492 KB Execution killed with signal 11
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
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 312 ms 1604 KB Output is correct
2 Correct 274 ms 1564 KB Output is correct
3 Correct 283 ms 1540 KB Output is correct
4 Correct 1339 ms 1492 KB Output is correct
5 Correct 1084 ms 1436 KB Output is correct
6 Correct 875 ms 1340 KB Output is correct
7 Correct 738 ms 1308 KB Output is correct
8 Correct 481 ms 1316 KB Output is correct
9 Correct 473 ms 1316 KB Output is correct
10 Correct 593 ms 1268 KB Output is correct
11 Correct 509 ms 1248 KB Output is correct
12 Correct 40 ms 1216 KB Output is correct
13 Correct 1649 ms 1512 KB Output is correct
14 Correct 1790 ms 1508 KB Output is correct
15 Correct 1800 ms 1512 KB Output is correct
16 Correct 1219 ms 1504 KB Output is correct
17 Correct 1342 ms 1500 KB Output is correct
18 Correct 513 ms 1236 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 673 ms 1260 KB Output is correct
2 Correct 214 ms 1208 KB Output is correct
3 Correct 390 ms 1312 KB Output is correct
4 Correct 396 ms 1300 KB Output is correct
5 Correct 553 ms 1316 KB Output is correct
6 Correct 458 ms 1292 KB Output is correct
7 Correct 478 ms 1292 KB Output is correct
8 Correct 322 ms 1256 KB Output is correct
9 Correct 25 ms 1224 KB Output is correct
10 Correct 848 ms 1508 KB Output is correct
11 Correct 832 ms 1372 KB Output is correct
12 Correct 832 ms 1236 KB Output is correct
13 Correct 661 ms 1172 KB Output is correct
14 Correct 390 ms 1108 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 1492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -