oj.uz

Submission #852308

# Submission time Handle Problem Language Result Execution time Memory
852308 2023-09-21T14:52:01 Z abcvuitunggio Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 36948 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
pair <int, int> edge[300001];
int a[300001],b[300001],mx[150001],mx2[150001],nxt[300001],ch[300001],t[300001],id,cycle[300001],d[300001],cnt[300001],res;
vector <int> ke[300001],ve[300001],tmp;
void dfs(int u, int i){
    ch[i]|=t[u];
    b[u]=a[u];
    for (int v:ke[u]){
        d[v]=d[u]+1;
        dfs(v,i);
        b[u]|=b[v];
    }
}
void dfs2(int u, int k, int i, int p, int sz){
    if (!b[u])
        return;
    cnt[d[u]]+=t[u];
    if (a[u]){
        if (d[u]>=k)
            res+=(!!cnt[d[u]-k]);
        else
            res+=t[ve[i][(p+k-d[u])%sz]];
    }
    for (int v:ke[u])
        dfs2(v,k,i,p,sz);
    cnt[d[u]]-=t[u];
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    for (int i=0;i<M;i++){
        edge[M-i-1]={R[i][0],R[i][1]};
        edge[M*2-i-1]={R[i][1],R[i][0]};
    }
    memset(mx,-1,sizeof(mx));
    memset(mx2,-1,sizeof(mx2));
    for (int i=0;i<M*2;i++){
        int u=edge[i].first;
        if (mx[u]%M<i%M){
            mx2[u]=mx[u];
            mx[u]=i;
        }
        else if (mx2[u]%M<i%M)
            mx2[u]=i;
    }
    for (int i=0;i<N;i++)
        a[mx[i]]=1;
    for (int i=0;i<M*2;i++){
        int v=edge[i].second;
        if (mx[v]%M==i%M)
            nxt[i]=(mx2[v]==-1?mx[v]:mx2[v]);
        else
            nxt[i]=mx[v];
        t[i]=(v==P);
    }
    for (int i=0;i<M*2;i++){
        if (!ch[i]){
            tmp.clear();
            int u=i;
            while (true){
                u=nxt[u];
                if (ch[u]>1){
                    for (int j:tmp)
                        ch[j]=2;
                    break;
                }
                if (ch[u]==1){
                    int p=0;
                    for (int j=0;j<tmp.size();j++)
                        if (tmp[j]==u)
                            p=j;
                    for (int j=p;j<tmp.size();j++){
                        ve[id].push_back(tmp[j]);
                        cycle[tmp[j]]=1;
                    }
                    for (int j:tmp)
                        ch[j]=2;
                    id++;
                    break;
                }
                tmp.push_back(u);
                ch[u]=1;
            }
        }
    }
    for (int i=0;i<M*2;i++)
        if (!cycle[i])
            ke[nxt[i]].push_back(i);
    for (int i=0;i<id;i++){
        ch[i]=0;
        for (int j:ve[i])
            dfs(j,i);
    }
    for (int i=0;i<Q;i++){
        res=0;
        for (int j=0;j<id;j++)
            if (ch[j])
                for (int k=0;k<ve[j].size();k++)
                    dfs2(ve[j][k],G[i]-1,j,k,ve[j].size());
        answer(res);
    }
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:70:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                     for (int j=0;j<tmp.size();j++)
      |                                  ~^~~~~~~~~~~
garden.cpp:73:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                     for (int j=p;j<tmp.size();j++){
      |                                  ~^~~~~~~~~~~
garden.cpp:99:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                 for (int k=0;k<ve[j].size();k++)
      |                              ~^~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 5 ms 27260 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27484 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 7 ms 27228 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 5 ms 27260 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27484 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 7 ms 27228 KB Output is correct
10 Correct 6 ms 27228 KB Output is correct
11 Correct 11 ms 29828 KB Output is correct
12 Correct 24 ms 29552 KB Output is correct
13 Correct 24 ms 30796 KB Output is correct
14 Correct 85 ms 34952 KB Output is correct
15 Correct 118 ms 35184 KB Output is correct
16 Correct 87 ms 33404 KB Output is correct
17 Correct 70 ms 33912 KB Output is correct
18 Correct 25 ms 31324 KB Output is correct
19 Correct 85 ms 35032 KB Output is correct
20 Correct 110 ms 35448 KB Output is correct
21 Correct 93 ms 34624 KB Output is correct
22 Correct 76 ms 33104 KB Output is correct
23 Correct 82 ms 35152 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 5 ms 27260 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27484 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 7 ms 27228 KB Output is correct
10 Correct 6 ms 27228 KB Output is correct
11 Correct 11 ms 29828 KB Output is correct
12 Correct 24 ms 29552 KB Output is correct
13 Correct 24 ms 30796 KB Output is correct
14 Correct 85 ms 34952 KB Output is correct
15 Correct 118 ms 35184 KB Output is correct
16 Correct 87 ms 33404 KB Output is correct
17 Correct 70 ms 33912 KB Output is correct
18 Correct 25 ms 31324 KB Output is correct
19 Correct 85 ms 35032 KB Output is correct
20 Correct 110 ms 35448 KB Output is correct
21 Correct 93 ms 34624 KB Output is correct
22 Correct 76 ms 33104 KB Output is correct
23 Correct 82 ms 35152 KB Output is correct
24 Correct 5 ms 27224 KB Output is correct
25 Correct 63 ms 29788 KB Output is correct
26 Correct 56 ms 29808 KB Output is correct
27 Correct 1473 ms 31808 KB Output is correct
28 Correct 1822 ms 36720 KB Output is correct
29 Execution timed out 5102 ms 36948 KB Time limit exceeded
30 Halted 0 ms 0 KB -