oj.uz

Submission #121506

# Submission time Handle Problem Language Result Execution time Memory
121506 2019-06-26T15:26:49 Z baqargam Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 25140 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];
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){
    if(k<dis) return;
    if((x&1)==0 && abs(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(*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];
        for(int j=0;j<(n<<1);j++)
            fx[j]=0;
        res=0;
        sz=sz1;dfs((p<<1),0,(p<<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 7 ms 11000 KB Output is correct
2 Correct 12 ms 10972 KB Output is correct
3 Correct 12 ms 10968 KB Output is correct
4 Correct 11 ms 10972 KB Output is correct
5 Correct 12 ms 10896 KB Output is correct
6 Correct 12 ms 11128 KB Output is correct
7 Correct 12 ms 10976 KB Output is correct
8 Correct 12 ms 11000 KB Output is correct
9 Correct 14 ms 11256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11000 KB Output is correct
2 Correct 12 ms 10972 KB Output is correct
3 Correct 12 ms 10968 KB Output is correct
4 Correct 11 ms 10972 KB Output is correct
5 Correct 12 ms 10896 KB Output is correct
6 Correct 12 ms 11128 KB Output is correct
7 Correct 12 ms 10976 KB Output is correct
8 Correct 12 ms 11000 KB Output is correct
9 Correct 14 ms 11256 KB Output is correct
10 Correct 12 ms 10972 KB Output is correct
11 Correct 25 ms 13152 KB Output is correct
12 Correct 46 ms 14716 KB Output is correct
13 Correct 67 ms 25128 KB Output is correct
14 Correct 147 ms 23032 KB Output is correct
15 Correct 182 ms 23376 KB Output is correct
16 Correct 145 ms 20484 KB Output is correct
17 Correct 132 ms 19708 KB Output is correct
18 Correct 48 ms 14772 KB Output is correct
19 Correct 149 ms 23100 KB Output is correct
20 Correct 191 ms 23376 KB Output is correct
21 Correct 151 ms 20540 KB Output is correct
22 Correct 130 ms 19652 KB Output is correct
23 Correct 221 ms 24204 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11000 KB Output is correct
2 Correct 12 ms 10972 KB Output is correct
3 Correct 12 ms 10968 KB Output is correct
4 Correct 11 ms 10972 KB Output is correct
5 Correct 12 ms 10896 KB Output is correct
6 Correct 12 ms 11128 KB Output is correct
7 Correct 12 ms 10976 KB Output is correct
8 Correct 12 ms 11000 KB Output is correct
9 Correct 14 ms 11256 KB Output is correct
10 Correct 12 ms 10972 KB Output is correct
11 Correct 25 ms 13152 KB Output is correct
12 Correct 46 ms 14716 KB Output is correct
13 Correct 67 ms 25128 KB Output is correct
14 Correct 147 ms 23032 KB Output is correct
15 Correct 182 ms 23376 KB Output is correct
16 Correct 145 ms 20484 KB Output is correct
17 Correct 132 ms 19708 KB Output is correct
18 Correct 48 ms 14772 KB Output is correct
19 Correct 149 ms 23100 KB Output is correct
20 Correct 191 ms 23376 KB Output is correct
21 Correct 151 ms 20540 KB Output is correct
22 Correct 130 ms 19652 KB Output is correct
23 Correct 221 ms 24204 KB Output is correct
24 Correct 14 ms 10900 KB Output is correct
25 Correct 156 ms 13144 KB Output is correct
26 Correct 176 ms 14684 KB Output is correct
27 Execution timed out 5041 ms 25140 KB Time limit exceeded
28 Halted 0 ms 0 KB -