oj.uz

Submission #154402

# Submission time Handle Problem Language Result Execution time Memory
154402 2019-09-21T17:20:03 Z davitmarg Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 124588 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<=30;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<=30;j++)
        {
            if(K%2)
                s.PB(j);
            K/=2;
        }
        for(int i=1;i<=2*n;i++)
            for(int j=0;j<=30;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 4572 KB Output is correct
3 Correct 6 ms 4728 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3904 KB Output is correct
6 Correct 6 ms 4728 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 7 ms 4728 KB Output is correct
9 Correct 8 ms 4984 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4572 KB Output is correct
3 Correct 6 ms 4728 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3904 KB Output is correct
6 Correct 6 ms 4728 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 7 ms 4728 KB Output is correct
9 Correct 8 ms 4984 KB Output is correct
10 Correct 5 ms 3960 KB Output is correct
11 Correct 46 ms 21916 KB Output is correct
12 Correct 97 ms 34668 KB Output is correct
13 Correct 308 ms 71884 KB Output is correct
14 Correct 561 ms 112732 KB Output is correct
15 Correct 551 ms 114188 KB Output is correct
16 Correct 316 ms 79180 KB Output is correct
17 Correct 253 ms 67548 KB Output is correct
18 Correct 93 ms 34524 KB Output is correct
19 Correct 598 ms 112808 KB Output is correct
20 Correct 551 ms 114140 KB Output is correct
21 Correct 317 ms 78924 KB Output is correct
22 Correct 239 ms 67396 KB Output is correct
23 Correct 456 ms 124588 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4572 KB Output is correct
3 Correct 6 ms 4728 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3904 KB Output is correct
6 Correct 6 ms 4728 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 7 ms 4728 KB Output is correct
9 Correct 8 ms 4984 KB Output is correct
10 Correct 5 ms 3960 KB Output is correct
11 Correct 46 ms 21916 KB Output is correct
12 Correct 97 ms 34668 KB Output is correct
13 Correct 308 ms 71884 KB Output is correct
14 Correct 561 ms 112732 KB Output is correct
15 Correct 551 ms 114188 KB Output is correct
16 Correct 316 ms 79180 KB Output is correct
17 Correct 253 ms 67548 KB Output is correct
18 Correct 93 ms 34524 KB Output is correct
19 Correct 598 ms 112808 KB Output is correct
20 Correct 551 ms 114140 KB Output is correct
21 Correct 317 ms 78924 KB Output is correct
22 Correct 239 ms 67396 KB Output is correct
23 Correct 456 ms 124588 KB Output is correct
24 Correct 23 ms 4056 KB Output is correct
25 Execution timed out 5003 ms 22012 KB Time limit exceeded
26 Halted 0 ms 0 KB -