Submission #942304

#	Time	Username	Problem	Language	Result	Execution time	Memory
942304		groshi	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1016 ms	421548 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;
struct wi{
    vector<int> Q,rev;
    vector<pair<int,int> >  top;
    int zle=-1;
    int wziety=0;
    int odl=0;
}*w;
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m,zap,x,y;
    cin>>n>>m>>zap;
    w=new wi[n+3];
    int pierw=sqrt(n);
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        w[x].Q.push_back(y);
        w[y].rev.push_back(x);
    }
    int kontrola=1;
    for(int i=1;i<=n;i++)
    {
        w[i].top.push_back({-1,i});
        for(int j=0;j<w[i].rev.size();j++)
        {
            int pom=w[i].rev[j];
            vector<pair<int,int> > pomoc;
            int l=0,r=0;
            kontrola++;
            while(pomoc.size()<pierw && (l<w[i].top.size() || r<w[pom].top.size()))
            {
                if(l<w[i].top.size() && w[w[i].top[l].second].wziety==kontrola)
                {
                    l++;
                    continue;
                }
                if(r<w[pom].top.size() && w[w[pom].top[r].second].wziety==kontrola)
                {
                    r++;
                    continue;
                }
                if(l==w[i].top.size())
                    pomoc.push_back(w[pom].top[r]),r++,w[w[pom].top[r-1].second].wziety=kontrola;
                else if(r==w[pom].top.size())
                    pomoc.push_back(w[i].top[l]),l++,w[w[i].top[l-1].second].wziety=kontrola;
                else if(w[i].top[l].first>w[pom].top[r].first)
                    pomoc.push_back(w[i].top[l]),l++,w[w[i].top[l-1].second].wziety=kontrola;
                else pomoc.push_back(w[pom].top[r]),r++,w[w[pom].top[r-1].second].wziety=kontrola;
            }
            swap(w[i].top,pomoc);
        }
        for(int j=0;j<w[i].top.size();j++)
            w[i].top[j].first++;
    }
    while(zap--)
    {
        int gdzie,ile;
        cin>>gdzie>>ile;
        for(int i=0;i<ile;i++)
        {
            cin>>x;
            w[x].zle=zap;
        }
        if(ile<pierw)
        {
            int wynik=-1;
            for(int i=0;i<w[gdzie].top.size();i++)
                if(w[w[gdzie].top[i].second].zle!=zap)
                    wynik=max(wynik,w[gdzie].top[i].first);
            cout<<wynik<<"\n";
        }
        else{
            int wynik=-1;
            for(int i=gdzie;i>=1;i--)
            {
                w[i].odl=-1e9;
                if(i==gdzie)
                    w[i].odl=0;
                for(int j=0;j<w[i].Q.size();j++)
                {
                    int pom=w[i].Q[j];
                    if(pom>gdzie)
                        continue;
                    w[i].odl=max(w[i].odl,w[pom].odl+1);
                }
                if(w[i].zle!=zap)
                    wynik=max(wynik,w[i].odl);
            }
            cout<<wynik<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int j=0;j<w[i].rev.size();j++)
      |                     ~^~~~~~~~~~~~~~~~
bitaro.cpp:36:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |             while(pomoc.size()<pierw && (l<w[i].top.size() || r<w[pom].top.size()))
      |                   ~~~~~~~~~~~~^~~~~~
bitaro.cpp:36:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             while(pomoc.size()<pierw && (l<w[i].top.size() || r<w[pom].top.size()))
      |                                          ~^~~~~~~~~~~~~~~~
bitaro.cpp:36:64: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             while(pomoc.size()<pierw && (l<w[i].top.size() || r<w[pom].top.size()))
      |                                                               ~^~~~~~~~~~~~~~~~~~
bitaro.cpp:38:21: 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 |                 if(l<w[i].top.size() && w[w[i].top[l].second].wziety==kontrola)
      |                    ~^~~~~~~~~~~~~~~~
bitaro.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                 if(r<w[pom].top.size() && w[w[pom].top[r].second].wziety==kontrola)
      |                    ~^~~~~~~~~~~~~~~~~~
bitaro.cpp:48:21: 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(l==w[i].top.size())
      |                    ~^~~~~~~~~~~~~~~~~
bitaro.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |                 else if(r==w[pom].top.size())
      |                         ~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int j=0;j<w[i].top.size();j++)
      |                     ~^~~~~~~~~~~~~~~~
bitaro.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for(int i=0;i<w[gdzie].top.size();i++)
      |                         ~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:85:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 for(int j=0;j<w[i].Q.size();j++)
      |                             ~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86