oj.uz

Submission #121476

# Submission time Handle Problem Language Result Execution time Memory
121476 2019-06-26T14:28:21 Z baqargam Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 31928 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[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 15 ms 14580 KB Output is correct
2 Correct 16 ms 14556 KB Output is correct
3 Correct 16 ms 14620 KB Output is correct
4 Correct 16 ms 14428 KB Output is correct
5 Correct 15 ms 14480 KB Output is correct
6 Correct 16 ms 14656 KB Output is correct
7 Correct 16 ms 14484 KB Output is correct
8 Correct 16 ms 14588 KB Output is correct
9 Correct 19 ms 14684 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14580 KB Output is correct
2 Correct 16 ms 14556 KB Output is correct
3 Correct 16 ms 14620 KB Output is correct
4 Correct 16 ms 14428 KB Output is correct
5 Correct 15 ms 14480 KB Output is correct
6 Correct 16 ms 14656 KB Output is correct
7 Correct 16 ms 14484 KB Output is correct
8 Correct 16 ms 14588 KB Output is correct
9 Correct 19 ms 14684 KB Output is correct
10 Correct 15 ms 14456 KB Output is correct
11 Correct 30 ms 16632 KB Output is correct
12 Correct 64 ms 18140 KB Output is correct
13 Correct 86 ms 31928 KB Output is correct
14 Correct 170 ms 26444 KB Output is correct
15 Correct 207 ms 26792 KB Output is correct
16 Correct 158 ms 23996 KB Output is correct
17 Correct 143 ms 23368 KB Output is correct
18 Correct 50 ms 18184 KB Output is correct
19 Correct 151 ms 26424 KB Output is correct
20 Correct 215 ms 26936 KB Output is correct
21 Correct 158 ms 23820 KB Output is correct
22 Correct 152 ms 23152 KB Output is correct
23 Correct 150 ms 27424 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14580 KB Output is correct
2 Correct 16 ms 14556 KB Output is correct
3 Correct 16 ms 14620 KB Output is correct
4 Correct 16 ms 14428 KB Output is correct
5 Correct 15 ms 14480 KB Output is correct
6 Correct 16 ms 14656 KB Output is correct
7 Correct 16 ms 14484 KB Output is correct
8 Correct 16 ms 14588 KB Output is correct
9 Correct 19 ms 14684 KB Output is correct
10 Correct 15 ms 14456 KB Output is correct
11 Correct 30 ms 16632 KB Output is correct
12 Correct 64 ms 18140 KB Output is correct
13 Correct 86 ms 31928 KB Output is correct
14 Correct 170 ms 26444 KB Output is correct
15 Correct 207 ms 26792 KB Output is correct
16 Correct 158 ms 23996 KB Output is correct
17 Correct 143 ms 23368 KB Output is correct
18 Correct 50 ms 18184 KB Output is correct
19 Correct 151 ms 26424 KB Output is correct
20 Correct 215 ms 26936 KB Output is correct
21 Correct 158 ms 23820 KB Output is correct
22 Correct 152 ms 23152 KB Output is correct
23 Correct 150 ms 27424 KB Output is correct
24 Correct 17 ms 14476 KB Output is correct
25 Correct 159 ms 16652 KB Output is correct
26 Correct 116 ms 18236 KB Output is correct
27 Execution timed out 5018 ms 31812 KB Time limit exceeded
28 Halted 0 ms 0 KB -