oj.uz

Submission #1084372

# Submission time Handle Problem Language Result Execution time Memory
1084372 2024-09-06T06:48:06 Z DucNguyen2007 Bitaro’s Party (JOI18_bitaro) C++14
0 / 100
 4 ms 5980 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e5+5;
const ll inf=2e18;
int n,m,q,dp[maxN+1],block;
vector<int> adj[maxN+1],topo;
vector<pii> vec[maxN+1];
map<int,int> mp;
bool vis[maxN+1];
void dfs(int u)
{
    vis[u]=true;
    for(auto v:adj[u])
    {
        if(!vis[v])
        {
            dfs(v);
        }
    }
    topo.push_back(u);
}
void meg(int u,int v)
{
    vector<pii> vt;
    int i=0,j=0;
    for(auto i:vec[u])
    {
        vis[i.fi]=false;
    }
    for(auto i:vec[v])
    {
        vis[i.fi]=false;
    }
    while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
    {
        while(i<vec[u].size()&&vis[vec[u][i].fi])
        {
            i++;
        }
        while(j<vec[v].size()&&vis[vec[v][j].fi])
        {
            j++;
        }
        int p1=vec[u][i].se,p2=vec[v][j].se;
        if(p1+1>=p2)
        {
            vt.push_back({vec[u][i].fi,p1+1});
            vis[vec[u][i].fi]=true;
            i++;
        }
        else
        {
            vt.push_back({vec[v][j].fi,p2});
            vis[vec[v][j].fi]=true;
            j++;
        }
    }
    while(i<vec[u].size()&&vt.size()<block)
    {
        while(i<vec[u].size()&&vis[vec[u][i].fi])
        {
            i++;
        }
        vt.push_back({vec[u][i].fi,vec[u][i].se+1});
        i++;
    }
    while(j<vec[v].size()&&vt.size()<block)
    {
        while(j<vec[v].size()&&vis[vec[v][j].fi])
        {
            j++;
        }
        vt.push_back({vec[v][j].fi,vec[v][j].se});
        j++;
    }
    vec[v]=vt;
}
void make()
{
    for(auto u:topo)
    {
        vec[u].push_back({u,0});
        for(auto v:adj[u])
        {
            //cout<<u<<" "<<v<<'\n';
            meg(u,v);
        }
    }
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
    }
    block=sqrt(n);
    dfs(1);
    memset(dp,0,sizeof(dp));
    reverse(topo.begin(),topo.end());
    make();
    while(q--)
    {
        int t,y;
        cin>>t>>y;
        if(y>=block)
        {
            for(int i=1;i<=n;i++)
            {
                dp[i]=0;
            }
        }
        for(int i=1;i<=y;i++)
        {
            int u;
            cin>>u;
            dp[u]=INT_MIN;
            if(y<block)
            {
                mp[u]++;
            }
        }
        if(y>=block)
        {
            for(auto u:topo)
            {
                for(auto v:adj[u])
                {
                    dp[v]=max(dp[v],dp[u]+1);
                }
            }
            if(dp[t]<0)
            {
                cout<<-1;
            }
            else cout<<dp[t];
        }
        else
        {
            int ans=-1;
            for(auto u:vec[t])
            {
                if(mp.find(u.fi)==mp.end())
                {
                    ans=u.se;
                    break;
                }
            }
            cout<<ans;
        }
        cout<<'\n';
        mp.clear();
    }
}

Compilation message

bitaro.cpp: In function 'void meg(int, int)':
bitaro.cpp:39:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:39:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |                            ~^~~~~~~~~~~~~~
bitaro.cpp:39:54: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |                                             ~~~~~~~~~^~~~~~
bitaro.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         while(i<vec[u].size()&&vis[vec[u][i].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while(j<vec[v].size()&&vis[vec[v][j].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:63:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while(i<vec[u].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:63:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     while(i<vec[u].size()&&vt.size()<block)
      |                            ~~~~~~~~~^~~~~~
bitaro.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         while(i<vec[u].size()&&vis[vec[u][i].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:72:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     while(j<vec[v].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:72:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     while(j<vec[v].size()&&vt.size()<block)
      |                            ~~~~~~~~~^~~~~~
bitaro.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while(j<vec[v].size()&&vis[vec[v][j].fi])
      |               ~^~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5464 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 2 ms 5468 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 3 ms 5724 KB Output is correct
7 Incorrect 4 ms 5724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5464 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 2 ms 5468 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 3 ms 5724 KB Output is correct
7 Incorrect 4 ms 5724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5464 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 2 ms 5468 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 3 ms 5724 KB Output is correct
7 Incorrect 4 ms 5724 KB Output isn't correct
8 Halted 0 ms 0 KB -