Submission #1084805

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1084805	2024-09-07T03:39:13 Z	DucNguyen2007	Bitaro’s Party (JOI18_bitaro)	C++14	Compilation error	0 ms	0 KB

bitaro

#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,a[maxN+1],cnt[maxN+1];
vector<int> adj[maxN+1],topo;
vector<pii> vec[maxN+1];
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++;
        }
        if(i>=vec[u].size()||j>=vec[v].size())
        {
            break;
        }
        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++;
        }
        if(i>=vec[u].size())
        {
            break;
        }
        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++;
        }
        if(j>=vec[v].size())
        {
            break;
        }
        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()
{
    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);
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs(i);
        }
    }
    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;
            a[i]=u;
            dp[u]=INT_MIN;
            if(y<block)
            {
                cnt[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(!cnt[u.fi])
                {
                    ans=u.se;
                    break;
                }
            }
            cout<<ans;
        }
        cout<<'\n';
        for(int i=1;i<=y;i++)
        {
            cnt[a[i]]=0;
        }
    }
}
/*4 8 5
2 3
2 3
1 3
1 3
3 4
1 2
1 2
1 2
2 1 4
1 3 4 2 2
3 4 1 1 4 2
4 2 1 3
3 1 4*/
#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,a[maxN+1],cnt[maxN+1];
vector<int> adj[maxN+1],topo;
vector<pii> vec[maxN+1];
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++;
        }
        if(i>=vec[u].size()||j>=vec[v].size())
        {
            break;
        }
        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++;
        }
        if(i>=vec[u].size())
        {
            break;
        }
        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++;
        }
        if(j>=vec[v].size())
        {
            break;
        }
        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()
{
    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);
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs(i);
        }
    }
    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;
            a[i]=u;
            dp[u]=INT_MIN;
            if(y<block)
            {
                cnt[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(!cnt[u.fi])
                {
                    ans=u.se;
                    break;
                }
            }
            cout<<ans;
        }
        cout<<'\n';
        for(int i=1;i<=y;i++)
        {
            cnt[a[i]]=0;
        }
    }
}

Compilation message

bitaro.cpp: In function 'void meg(int, int)':
bitaro.cpp:38: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]
   38 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:38: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]
   38 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |                            ~^~~~~~~~~~~~~~
bitaro.cpp:38: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]
   38 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |                                             ~~~~~~~~~^~~~~~
bitaro.cpp:40: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]
   40 |         while(i<vec[u].size()&&vis[vec[u][i].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:44: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]
   44 |         while(j<vec[v].size()&&vis[vec[v][j].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:48:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if(i>=vec[u].size()||j>=vec[v].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp:48:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if(i>=vec[u].size()||j>=vec[v].size())
      |                              ~^~~~~~~~~~~~~~~
bitaro.cpp:66: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]
   66 |     while(i<vec[u].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:66: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]
   66 |     while(i<vec[u].size()&&vt.size()<block)
      |                            ~~~~~~~~~^~~~~~
bitaro.cpp:68: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]
   68 |         while(i<vec[u].size()&&vis[vec[u][i].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:72:13: 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 |         if(i>=vec[u].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp:79: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]
   79 |     while(j<vec[v].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:79: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]
   79 |     while(j<vec[v].size()&&vt.size()<block)
      |                            ~~~~~~~~~^~~~~~
bitaro.cpp:81: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]
   81 |         while(j<vec[v].size()&&vis[vec[v][j].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:85:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         if(j>=vec[v].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp: At global scope:
bitaro.cpp:207:11: error: redefinition of 'const int maxN'
  207 | const int maxN=1e5+5;
      |           ^~~~
bitaro.cpp:8:11: note: 'const int maxN' previously defined here
    8 | const int maxN=1e5+5;
      |           ^~~~
bitaro.cpp:208:10: error: redefinition of 'const long long int inf'
  208 | const ll inf=2e18;
      |          ^~~
bitaro.cpp:9:10: note: 'const long long int inf' previously defined here
    9 | const ll inf=2e18;
      |          ^~~
bitaro.cpp:209:5: error: redefinition of 'int n'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |     ^
bitaro.cpp:10:5: note: 'int n' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |     ^
bitaro.cpp:209:7: error: redefinition of 'int m'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |       ^
bitaro.cpp:10:7: note: 'int m' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |       ^
bitaro.cpp:209:9: error: redefinition of 'int q'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |         ^
bitaro.cpp:10:9: note: 'int q' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |         ^
bitaro.cpp:209:11: error: redefinition of 'int dp [100006]'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |           ^~
bitaro.cpp:10:11: note: 'int dp [100006]' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |           ^~
bitaro.cpp:209:22: error: redefinition of 'int block'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                      ^~~~~
bitaro.cpp:10:22: note: 'int block' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                      ^~~~~
bitaro.cpp:209:28: error: redefinition of 'int a [100006]'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                            ^
bitaro.cpp:10:28: note: 'int a [100006]' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                            ^
bitaro.cpp:209:38: error: redefinition of 'int cnt [100006]'
  209 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                                      ^~~
bitaro.cpp:10:38: note: 'int cnt [100006]' previously declared here
   10 | int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
      |                                      ^~~
bitaro.cpp:210:13: error: redefinition of 'std::vector<int> adj [100006]'
  210 | vector<int> adj[maxN+1],topo;
      |             ^~~
bitaro.cpp:11:13: note: 'std::vector<int> adj [100006]' previously declared here
   11 | vector<int> adj[maxN+1],topo;
      |             ^~~
bitaro.cpp:210:25: error: redefinition of 'std::vector<int> topo'
  210 | vector<int> adj[maxN+1],topo;
      |                         ^~~~
bitaro.cpp:11:25: note: 'std::vector<int> topo' previously declared here
   11 | vector<int> adj[maxN+1],topo;
      |                         ^~~~
bitaro.cpp:211:13: error: redefinition of 'std::vector<std::pair<int, int> > vec [100006]'
  211 | vector<pii> vec[maxN+1];
      |             ^~~
bitaro.cpp:12:13: note: 'std::vector<std::pair<int, int> > vec [100006]' previously declared here
   12 | vector<pii> vec[maxN+1];
      |             ^~~
bitaro.cpp:212:6: error: redefinition of 'bool vis [100006]'
  212 | bool vis[maxN+1];
      |      ^~~
bitaro.cpp:13:6: note: 'bool vis [100006]' previously declared here
   13 | bool vis[maxN+1];
      |      ^~~
bitaro.cpp:213:6: error: redefinition of 'void dfs(int)'
  213 | void dfs(int u)
      |      ^~~
bitaro.cpp:14:6: note: 'void dfs(int)' previously defined here
   14 | void dfs(int u)
      |      ^~~
bitaro.cpp:225:6: error: redefinition of 'void meg(int, int)'
  225 | void meg(int u,int v)
      |      ^~~
bitaro.cpp:26:6: note: 'void meg(int, int)' previously defined here
   26 | void meg(int u,int v)
      |      ^~~
bitaro.cpp: In function 'void meg(int, int)':
bitaro.cpp:237: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]
  237 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:237: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]
  237 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |                            ~^~~~~~~~~~~~~~
bitaro.cpp:237: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]
  237 |     while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
      |                                             ~~~~~~~~~^~~~~~
bitaro.cpp:239: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]
  239 |         while(i<vec[u].size()&&vis[vec[u][i].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:243: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]
  243 |         while(j<vec[v].size()&&vis[vec[v][j].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:247:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |         if(i>=vec[u].size()||j>=vec[v].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp:247:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |         if(i>=vec[u].size()||j>=vec[v].size())
      |                              ~^~~~~~~~~~~~~~~
bitaro.cpp:265: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]
  265 |     while(i<vec[u].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:265: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]
  265 |     while(i<vec[u].size()&&vt.size()<block)
      |                            ~~~~~~~~~^~~~~~
bitaro.cpp:267: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]
  267 |         while(i<vec[u].size()&&vis[vec[u][i].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:271:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |         if(i>=vec[u].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp:278: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]
  278 |     while(j<vec[v].size()&&vt.size()<block)
      |           ~^~~~~~~~~~~~~~
bitaro.cpp:278: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]
  278 |     while(j<vec[v].size()&&vt.size()<block)
      |                            ~~~~~~~~~^~~~~~
bitaro.cpp:280: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]
  280 |         while(j<vec[v].size()&&vis[vec[v][j].fi])
      |               ~^~~~~~~~~~~~~~
bitaro.cpp:284:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  284 |         if(j>=vec[v].size())
      |            ~^~~~~~~~~~~~~~~
bitaro.cpp: At global scope:
bitaro.cpp:293:6: error: redefinition of 'void make()'
  293 | void make()
      |      ^~~~
bitaro.cpp:94:6: note: 'void make()' previously defined here
   94 | void make()
      |      ^~~~
bitaro.cpp:305:5: error: redefinition of 'int main()'
  305 | int main()
      |     ^~~~
bitaro.cpp:106:5: note: 'int main()' previously defined here
  106 | int main()
      |     ^~~~