oj.uz

Submission #121474

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

using namespace std;

int d[300005],a,k,n,m,q,p,c[300005],d2[300005],v1[300005],sz,sz1,sz2,st,fx[300005],ch,res[2005];
vector<pair<int,int> >v[300005];
vector<int>rv[300005];
set<int>s;

void cch(int x,int dis,int st){
    for(int i=0;i<rv[x].size();i++){
        if(rv[x][i]==st) {sz=dis+1;return;}
        cch(rv[x][i],dis+1,st);
    }
}

void dfs(int x,int dis,int st){
    //cout<<st<<" "<<x<<" "<<dis<<" "<<k<<" "<<sz<<endl;
    if(x%2==0 && abs(k-dis)%sz==0 && dis<=k)
    {
        s.insert(x);
    }
    for(int i=0;i<rv[x].size();i++){
        if(rv[x][i]==st) continue;
        dfs(rv[x][i],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
        int a=R[i][0];
        int b=R[i][1];
        v[a].push_back({i,b});
        v[b].push_back({i,a});
    }
    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++){
        //cout<<i<<" "<<v1[i]<<endl;
        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];
        s.clear();
        sz=sz1;dfs(2*p,0,2*p);
        sz=sz2;dfs(2*p+1,0,2*p+1);
        sz=s.size();
        answer(sz);
    }
}

Compilation message

garden.cpp: In function 'void cch(int, int, int)':
garden.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<rv[x].size();i++){
                 ~^~~~~~~~~~~~~
garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<rv[x].size();i++){
                 ~^~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14604 KB Output is correct
2 Correct 16 ms 14612 KB Output is correct
3 Correct 20 ms 14532 KB Output is correct
4 Correct 15 ms 14456 KB Output is correct
5 Correct 12 ms 14456 KB Output is correct
6 Correct 17 ms 14712 KB Output is correct
7 Correct 16 ms 14432 KB Output is correct
8 Correct 16 ms 14468 KB Output is correct
9 Correct 18 ms 14784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14604 KB Output is correct
2 Correct 16 ms 14612 KB Output is correct
3 Correct 20 ms 14532 KB Output is correct
4 Correct 15 ms 14456 KB Output is correct
5 Correct 12 ms 14456 KB Output is correct
6 Correct 17 ms 14712 KB Output is correct
7 Correct 16 ms 14432 KB Output is correct
8 Correct 16 ms 14468 KB Output is correct
9 Correct 18 ms 14784 KB Output is correct
10 Correct 15 ms 14456 KB Output is correct
11 Correct 28 ms 16608 KB Output is correct
12 Correct 45 ms 18176 KB Output is correct
13 Correct 90 ms 31808 KB Output is correct
14 Correct 152 ms 26400 KB Output is correct
15 Correct 193 ms 26936 KB Output is correct
16 Correct 151 ms 23960 KB Output is correct
17 Correct 159 ms 23384 KB Output is correct
18 Correct 51 ms 18128 KB Output is correct
19 Correct 152 ms 26404 KB Output is correct
20 Correct 186 ms 26888 KB Output is correct
21 Correct 170 ms 23784 KB Output is correct
22 Correct 164 ms 23052 KB Output is correct
23 Correct 169 ms 27472 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14604 KB Output is correct
2 Correct 16 ms 14612 KB Output is correct
3 Correct 20 ms 14532 KB Output is correct
4 Correct 15 ms 14456 KB Output is correct
5 Correct 12 ms 14456 KB Output is correct
6 Correct 17 ms 14712 KB Output is correct
7 Correct 16 ms 14432 KB Output is correct
8 Correct 16 ms 14468 KB Output is correct
9 Correct 18 ms 14784 KB Output is correct
10 Correct 15 ms 14456 KB Output is correct
11 Correct 28 ms 16608 KB Output is correct
12 Correct 45 ms 18176 KB Output is correct
13 Correct 90 ms 31808 KB Output is correct
14 Correct 152 ms 26400 KB Output is correct
15 Correct 193 ms 26936 KB Output is correct
16 Correct 151 ms 23960 KB Output is correct
17 Correct 159 ms 23384 KB Output is correct
18 Correct 51 ms 18128 KB Output is correct
19 Correct 152 ms 26404 KB Output is correct
20 Correct 186 ms 26888 KB Output is correct
21 Correct 170 ms 23784 KB Output is correct
22 Correct 164 ms 23052 KB Output is correct
23 Correct 169 ms 27472 KB Output is correct
24 Correct 17 ms 14456 KB Output is correct
25 Correct 160 ms 16664 KB Output is correct
26 Correct 117 ms 18232 KB Output is correct
27 Execution timed out 5088 ms 31824 KB Time limit exceeded
28 Halted 0 ms 0 KB -