oj.uz

Submission #154400

# Submission time Handle Problem Language Result Execution time Memory
154400 2019-09-21T17:17:58 Z davitmarg Tropical Garden (IOI11_garden) C++17
49 / 100
 288 ms 71256 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 dp[150005][32];
int dir[2*150005],nxt[2*150005][32];
vector<pair<int,int>> g[150005];
void addNode(int a,int b)
{
    dir[a]=b;
    //cout<<a<<" "<<b<<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].empty())
            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);
    }
    for(int i=1;i<=2*n;i++)
        nxt[i][0]=dir[i];

    for(int j=1;j<29;j++)
        for(int i=1;i<=2*n;i++)
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
            
    for(int k=1;k<=q;k++)
    {
        int K=c[k];
        vector<int> s;
        for(int j=0;j<=29;j++)
        {
            if(K%2)
                s.PB(j);
            K/=2;
        }
        for(int i=1;i<=2*n;i++)
            for(int j=0;j<=29;j++)
                dp[i][j]=0;
        for(int i=1;i<=n;i++)
            dp[nxt[i][s[0]]][0]++;
        
        for(int j=1;j<s.size();j++)
            for(int i=1;i<=2*n;i++)
                dp[ nxt[i][s[j]] ][j]+=dp[i][j-1];
        answer(dp[p][s.size()-1]+dp[p+n][s.size()-1]);
    }
    
}



#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
 
/*


2 1 0
0 1
1
1
 
*/

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<s.size();j++)
                     ~^~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4600 KB Output is correct
3 Correct 4 ms 4728 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4732 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 6 ms 4728 KB Output is correct
9 Correct 9 ms 4984 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4600 KB Output is correct
3 Correct 4 ms 4728 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4732 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 6 ms 4728 KB Output is correct
9 Correct 9 ms 4984 KB Output is correct
10 Correct 5 ms 3964 KB Output is correct
11 Correct 44 ms 21972 KB Output is correct
12 Correct 94 ms 34552 KB Output is correct
13 Incorrect 288 ms 71256 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4600 KB Output is correct
3 Correct 4 ms 4728 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4732 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 6 ms 4728 KB Output is correct
9 Correct 9 ms 4984 KB Output is correct
10 Correct 5 ms 3964 KB Output is correct
11 Correct 44 ms 21972 KB Output is correct
12 Correct 94 ms 34552 KB Output is correct
13 Incorrect 288 ms 71256 KB Output isn't correct
14 Halted 0 ms 0 KB -