oj.uz

Submission #121512

# Submission time Handle Problem Language Result Execution time Memory
121512 2019-06-26T15:38:04 Z baqargam Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 25968 KB 
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

int a,k,n,m,q,p,v1[300005],sz,sz1,sz2,st,ch,res;
bool fx[300005];
bool fx1[300005];
vector<pair<int,int> >v[150005];
vector<int>rv[300005];

inline void cch(int x,int dis,int st){
    for(vector<int> :: iterator it=rv[x].begin();it!=rv[x].end();it++){
        if(*it==st) {sz=dis+1;return;}
        cch(*it,dis+1,st);
    }
}

inline void dfs(int x,int dis,int st){
    fx1[x]=1;
    if(k<dis) return;
    if(!(x&1) && (k-dis)%sz==0)
    {
        res+=(1^fx[x]);
        fx[x]=1;
    }
    for(vector<int> :: iterator it=rv[x].begin();it!=rv[x].end();it++){
        if(fx[*it]) continue;
        if(*it==st) continue;
        dfs(*it,dis+1,st);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int n=N,m=M,p=P,i;
    for(i=0;i<m;i++){///grafi1
        v[R[i][0]].push_back({i,R[i][1]});
        v[R[i][1]].push_back({i,R[i][0]});
    }
    for(i=0;i<n;i++){
        sort(v[i].begin(),v[i].end());
    }
    for(i=0;i<n;i++){///grafi2
        if(v[i].size()==1)
        {
            int to=v[i][0].second;
            int val=v[i][0].first;
            if(v[to][0].first==val)
                v1[(i<<1)^1]=(to<<1)^1;
            else
                v1[(i<<1)^1]=(to<<1);

            if(v[to][0].first==val)
                v1[(i<<1)]=(to<<1)^1;
            else
                v1[(i<<1)]=(to<<1);
        }
        else
        {
            int to=v[i][0].second;
            int val=v[i][0].first;
//            cout<<i<<" "<<to<<" "<<val<<" "<<v[to][0].first<<endl;
            if(v[to][0].first==val)
                v1[(i<<1)]=(to<<1)^1;
            else
                v1[(i<<1)]=(to<<1);

            to=v[i][1].second;
            val=v[i][1].first;
//            cout<<i<<" "<<to<<" "<<val<<" "<<v[to][0].first<<endl;
            if(v[to][0].first==val)
                v1[(i<<1)^1]=(to<<1)^1;
            else
                v1[(i<<1)^1]=(to<<1);

        }
    }

    for(i=0;i<2*n;i++){
        rv[v1[i]].push_back(i);
    }

    sz=1000000003;cch(2*p,0,2*p);sz1=sz;
    sz=1000000003;cch(2*p+1,0,2*p+1);sz2=sz;

    for(i=0; i<Q; i++)
    {
        k=G[i];
        memset (fx,0,n<<1);
        res=0;
        memset (fx1,0,n<<1);sz=sz1;dfs((p<<1),0,(p<<1));
        memset (fx1,0,n<<1);sz=sz2;dfs((p<<1)^1,0,(p<<1)^1);
        answer(res);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11000 KB Output is correct
2 Correct 12 ms 11000 KB Output is correct
3 Correct 12 ms 11092 KB Output is correct
4 Correct 12 ms 10928 KB Output is correct
5 Correct 12 ms 10972 KB Output is correct
6 Correct 13 ms 11128 KB Output is correct
7 Correct 12 ms 10896 KB Output is correct
8 Correct 12 ms 11108 KB Output is correct
9 Correct 15 ms 11196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11000 KB Output is correct
2 Correct 12 ms 11000 KB Output is correct
3 Correct 12 ms 11092 KB Output is correct
4 Correct 12 ms 10928 KB Output is correct
5 Correct 12 ms 10972 KB Output is correct
6 Correct 13 ms 11128 KB Output is correct
7 Correct 12 ms 10896 KB Output is correct
8 Correct 12 ms 11108 KB Output is correct
9 Correct 15 ms 11196 KB Output is correct
10 Correct 12 ms 10844 KB Output is correct
11 Correct 26 ms 13192 KB Output is correct
12 Correct 54 ms 14856 KB Output is correct
13 Correct 67 ms 25912 KB Output is correct
14 Correct 219 ms 23372 KB Output is correct
15 Correct 228 ms 23644 KB Output is correct
16 Correct 155 ms 20784 KB Output is correct
17 Correct 146 ms 19768 KB Output is correct
18 Correct 46 ms 14780 KB Output is correct
19 Correct 217 ms 23340 KB Output is correct
20 Correct 194 ms 23648 KB Output is correct
21 Correct 156 ms 20648 KB Output is correct
22 Correct 163 ms 19808 KB Output is correct
23 Correct 159 ms 24468 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11000 KB Output is correct
2 Correct 12 ms 11000 KB Output is correct
3 Correct 12 ms 11092 KB Output is correct
4 Correct 12 ms 10928 KB Output is correct
5 Correct 12 ms 10972 KB Output is correct
6 Correct 13 ms 11128 KB Output is correct
7 Correct 12 ms 10896 KB Output is correct
8 Correct 12 ms 11108 KB Output is correct
9 Correct 15 ms 11196 KB Output is correct
10 Correct 12 ms 10844 KB Output is correct
11 Correct 26 ms 13192 KB Output is correct
12 Correct 54 ms 14856 KB Output is correct
13 Correct 67 ms 25912 KB Output is correct
14 Correct 219 ms 23372 KB Output is correct
15 Correct 228 ms 23644 KB Output is correct
16 Correct 155 ms 20784 KB Output is correct
17 Correct 146 ms 19768 KB Output is correct
18 Correct 46 ms 14780 KB Output is correct
19 Correct 217 ms 23340 KB Output is correct
20 Correct 194 ms 23648 KB Output is correct
21 Correct 156 ms 20648 KB Output is correct
22 Correct 163 ms 19808 KB Output is correct
23 Correct 159 ms 24468 KB Output is correct
24 Correct 13 ms 10972 KB Output is correct
25 Correct 154 ms 13196 KB Output is correct
26 Correct 149 ms 14872 KB Output is correct
27 Execution timed out 5070 ms 25968 KB Time limit exceeded
28 Halted 0 ms 0 KB -