oj.uz

답안 #1065837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065837 2024-08-19T12:12:15 Z Faisal_Saqib 장난감 기차 (IOI17_train) C++17
0 / 100
 5 ms 1628 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vll vector<ll>
#define pb push_back
#define sll set<ll>

const int N=5e3+10;
vll ma[N];
bool alive[N],vis[N],lcp[N];
ll n,owner[N],m,deg[N],deg_[N];
vll attr(vll&a,ll player)
{
    ll sz=a.size();
    for(int i=1;i<=n;i++)
        if(alive[i])
        {
            vis[i]=0;
            deg_[i]=deg[i];
        }
    queue<int> q;
    for(auto&i:a)
        if(alive[i])
        {
            q.push(i);
            vis[i]=1;
        }
    vll ans;
    while(q.size())
    {
        int f=q.front();
        q.pop();
        ans.push_back(f);
        for(ll&y:ma[f])
        {
            if(!alive[y])continue;
            deg_[y]--;
            if(owner[y]==player)
            {
                if(!vis[y])
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
            else // Owned by other player
            {
                if(deg_[y]==0 and vis[y]==0)
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
    // cout<<endl;
    return ans;
}
vll Buchi(vll a)
{
    ll sz=a.size();
    while(true)
    {
        auto cur=attr(a,1);
        for(int i=1;i<=n;i++)lcp[i]=0;
        for(auto&i:cur)lcp[i]=1;
        cur.clear();
        for(int i=1;i<=n;i++)
            if(alive[i] and lcp[i])
                cur.push_back(i);
        if(cur.size()==0)break;
        cur=attr(cur,2);
        for(auto&i:cur){
            for(auto jp:ma[i])
                deg[jp]--;
            alive[i]=0;
            deg[i]=0;
            ma[i].clear();
        }
    }
    return a;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v)
{
    n=a.size();
    vll vertexs;
    for(int i=1;i<=n;i++)
    {
        alive[i]=1;
        if(a[i-1]==1)
            owner[i]=1;
        else
            owner[i]=2;
        if(r[i-1])
            vertexs.push_back(i);
    }
    m=u.size();
    for(int j=0;j<m;j++)
    {
        u[j]++;
        v[j]++;
        ma[v[j]].pb(u[j]); // Directed edges
        deg[u[j]]++;
    }
    Buchi(vertexs);
    vector<int> ap(n);
    for(int i=1;i<=n;i++)
        ap[i-1]=alive[i];
    return ap;
}

Compilation message

train.cpp: In function 'std::vector<long long int> attr(std::vector<long long int>&, long long int)':
train.cpp:15:8: warning: unused variable 'sz' [-Wunused-variable]
   15 |     ll sz=a.size();
      |        ^~
train.cpp: In function 'std::vector<long long int> Buchi(std::vector<long long int>)':
train.cpp:62:8: warning: unused variable 'sz' [-Wunused-variable]
   62 |     ll sz=a.size();
      |        ^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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