oj.uz

Submission #154388

# Submission time Handle Problem Language Result Execution time Memory
154388 2019-09-21T15:48:52 Z davitmarg Tropical Garden (IOI11_garden) C++17
0 / 100
 22 ms 11128 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin (),v.end()
using namespace std;

#ifndef death
    #include "garden.h"
#include "gardenlib.h"
#endif

#ifdef death
    void answer(int x)
    {
        cout<<"! "<<x<<endl;
    }
#endif

int n,m,p,q,c[2003],used[150005];
LL ans[150005],cnt[2][150005];
vector<int> g[2*150005];
vector<pair<int,int>> G[150005];
void addNode(int a,int b)
{
    g[b].PB(a);
    //cout<<b<<" "<<a<<endl;
}

void count_routes(int N,int M,int P,int R[][2] ,int Q,int K[])
{
    n=N;
    m=M;
    q=Q;
    p=P+1;
    for(int i=0;i<m;i++)
    {
        int a=R[i][0]+1,b=R[i][1]+1;
        G[a].PB(MP(i,b));
        G[b].PB(MP(i,a));
    }
    for(int i=1;i<=q;i++)
        c[i]=K[i-1];
    
    for(int i=1;i<=n;i++)
        sort(all(G[i]));

    for(int i=1;i<=n;i++)
    {
        int to;

        if(G[i].size()==0)
            continue;

        to=G[i][0].second;
        if(i==G[to][0].second)
            addNode(i,n+to);
        else    
            addNode(i,to);

        if(G[i].size()==1)
            to=G[i][0].second; 
        else
            to=G[i][1].second;

        if(i==G[to][0].second)
            addNode(i+n,to+n);
        else
            addNode(i+n,to);
    }

    vector<int> qu;
    qu.PB(p);
    cnt[0][p]=1;
    qu.PB(p+n);
    cnt[0][p+n]=1;
    for(int i=1;i<=n;i++)
    {  
        int now,lst;
        now=i%2;
        lst=!now;
        vector<int> V=qu;
        qu.clear();
        //cout<<i-1<<" v "<<endl;
        for(int j=0;j<V.size();j++)
        {
            int v=V[j];
            //cout<<v<<" : ";
            for(int k=0;k<g[v].size();k++)
            {
                int to=g[v][k];
                if(used[to]!=i)
                {
                    qu.PB(to);
                    cnt[now][to]=0;
                }
                used[to]=i;
                cnt[now][to]+=cnt[lst][v];
            }
        }
        //cout<<endl;
        for(int j=0;j<qu.size();j++)
            if(qu[j]<=n)
                ans[i]+=cnt[now][qu[j]];
    }
    for(int i=1;i<=q;i++)
        answer(ans[c[i]]);
}



#ifdef death

int main()
{
    int N,M,Q,P,R[102][2],K[102];
    cin>>N>>M>>P;
    for(int i=0;i<M;i++)
        cin>>R[i][0]>>R[i][1];
    cin>>Q;
    for(int i=0;i<Q;i++)
        cin>>K[i];
    count_routes(N,M,P,R,Q,K);
	return 0;
}

#endif
 
/*


 
 
*/

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:103:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<V.size();j++)
                     ~^~~~~~~~~
garden.cpp:107:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0;k<g[v].size();k++)
                         ~^~~~~~~~~~~~
garden.cpp:120:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<qu.size();j++)
                     ~^~~~~~~~~~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11000 KB Output is correct
2 Correct 22 ms 11128 KB Output is correct
3 Correct 22 ms 11128 KB Output is correct
4 Incorrect 11 ms 10872 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11000 KB Output is correct
2 Correct 22 ms 11128 KB Output is correct
3 Correct 22 ms 11128 KB Output is correct
4 Incorrect 11 ms 10872 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11000 KB Output is correct
2 Correct 22 ms 11128 KB Output is correct
3 Correct 22 ms 11128 KB Output is correct
4 Incorrect 11 ms 10872 KB Output isn't correct
5 Halted 0 ms 0 KB -