oj.uz

Submission #121496

# Submission time Handle Problem Language Result Execution time Memory
121496 2019-06-26T14:43:35 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;
    for(int 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(int i=0;i<n;i++){
        sort(v[i].begin(),v[i].end());
    }
    for(int 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[2*i+1]=2*to+1;
            else
                v1[2*i+1]=2*to;

            if(v[to][0].first==val)
                v1[2*i]=2*to+1;
            else
                v1[2*i]=2*to;
        }
        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[2*i]=2*to+1;
            else
                v1[2*i]=2*to;

            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[2*i+1]=2*to+1;
            else
                v1[2*i+1]=2*to;

        }
    }

    for(int 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(int i=0; i<Q; i++)
    {
        k=G[i];
        for(int j=0;j<2*n;j++)
            fx[j]=0;
        res=0;
        sz=sz1;dfs(2*p,0,2*p);
        sz=sz2;dfs(2*p+1,0,2*p+1);
        answer(res);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10972 KB Output is correct
2 Correct 12 ms 11260 KB Output is correct
3 Correct 12 ms 11000 KB Output is correct
4 Correct 12 ms 10904 KB Output is correct
5 Correct 12 ms 11000 KB Output is correct
6 Correct 12 ms 11128 KB Output is correct
7 Correct 12 ms 10872 KB Output is correct
8 Correct 12 ms 11000 KB Output is correct
9 Correct 12 ms 11196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10972 KB Output is correct
2 Correct 12 ms 11260 KB Output is correct
3 Correct 12 ms 11000 KB Output is correct
4 Correct 12 ms 10904 KB Output is correct
5 Correct 12 ms 11000 KB Output is correct
6 Correct 12 ms 11128 KB Output is correct
7 Correct 12 ms 10872 KB Output is correct
8 Correct 12 ms 11000 KB Output is correct
9 Correct 12 ms 11196 KB Output is correct
10 Correct 13 ms 10972 KB Output is correct
11 Correct 33 ms 13052 KB Output is correct
12 Correct 47 ms 14684 KB Output is correct
13 Correct 68 ms 25092 KB Output is correct
14 Correct 153 ms 23100 KB Output is correct
15 Correct 191 ms 23516 KB Output is correct
16 Correct 151 ms 20560 KB Output is correct
17 Correct 139 ms 19704 KB Output is correct
18 Correct 50 ms 14768 KB Output is correct
19 Correct 166 ms 23160 KB Output is correct
20 Correct 209 ms 23372 KB Output is correct
21 Correct 171 ms 20468 KB Output is correct
22 Correct 155 ms 19680 KB Output is correct
23 Correct 168 ms 24176 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10972 KB Output is correct
2 Correct 12 ms 11260 KB Output is correct
3 Correct 12 ms 11000 KB Output is correct
4 Correct 12 ms 10904 KB Output is correct
5 Correct 12 ms 11000 KB Output is correct
6 Correct 12 ms 11128 KB Output is correct
7 Correct 12 ms 10872 KB Output is correct
8 Correct 12 ms 11000 KB Output is correct
9 Correct 12 ms 11196 KB Output is correct
10 Correct 13 ms 10972 KB Output is correct
11 Correct 33 ms 13052 KB Output is correct
12 Correct 47 ms 14684 KB Output is correct
13 Correct 68 ms 25092 KB Output is correct
14 Correct 153 ms 23100 KB Output is correct
15 Correct 191 ms 23516 KB Output is correct
16 Correct 151 ms 20560 KB Output is correct
17 Correct 139 ms 19704 KB Output is correct
18 Correct 50 ms 14768 KB Output is correct
19 Correct 166 ms 23160 KB Output is correct
20 Correct 209 ms 23372 KB Output is correct
21 Correct 171 ms 20468 KB Output is correct
22 Correct 155 ms 19680 KB Output is correct
23 Correct 168 ms 24176 KB Output is correct
24 Correct 13 ms 10872 KB Output is correct
25 Correct 157 ms 13048 KB Output is correct
26 Correct 173 ms 14780 KB Output is correct
27 Execution timed out 5067 ms 25140 KB Time limit exceeded
28 Halted 0 ms 0 KB -