oj.uz

Submission #154401

# Submission time Handle Problem Language Result Execution time Memory
154401 2019-09-21T17:18:55 Z davitmarg Tropical Garden (IOI11_garden) C++17
49 / 100
 310 ms 71936 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];
LL dp[2*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 4444 KB Output is correct
2 Correct 7 ms 4572 KB Output is correct
3 Correct 6 ms 4776 KB Output is correct
4 Correct 5 ms 3836 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 4784 KB Output is correct
7 Correct 6 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 4444 KB Output is correct
2 Correct 7 ms 4572 KB Output is correct
3 Correct 6 ms 4776 KB Output is correct
4 Correct 5 ms 3836 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 4784 KB Output is correct
7 Correct 6 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 7 ms 3960 KB Output is correct
11 Correct 49 ms 21872 KB Output is correct
12 Correct 106 ms 34660 KB Output is correct
13 Incorrect 310 ms 71936 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 4444 KB Output is correct
2 Correct 7 ms 4572 KB Output is correct
3 Correct 6 ms 4776 KB Output is correct
4 Correct 5 ms 3836 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 4784 KB Output is correct
7 Correct 6 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 7 ms 3960 KB Output is correct
11 Correct 49 ms 21872 KB Output is correct
12 Correct 106 ms 34660 KB Output is correct
13 Incorrect 310 ms 71936 KB Output isn't correct
14 Halted 0 ms 0 KB -