oj.uz

Submission #852280

# Submission time Handle Problem Language Result Execution time Memory
852280 2023-09-21T14:15:11 Z abcvuitunggio Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 38228 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
pair <int, int> edge[300001];
int a[300001],mx[150001],mx2[150001],nxt[300001],ch[300001],target[300001],idx[300001],pos[300001],id,cycle[300001],d[300001],cnt[300001],res;
vector <int> ke[300001],ve[300001],tmp;
void dfs(int u, int k){
    cnt[d[u]]+=target[u];
    if (a[u]){
        if (d[u]>=k)
            res+=(!!cnt[d[u]-k]);
        else
            res+=target[ve[idx[u]][(pos[u]+k-d[u])%(ve[idx[u]].size())]];
    }
    for (int v:ke[u]){
        d[v]=d[u]+1;
        dfs(v,k);
    }
    cnt[d[u]]-=target[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];
        target[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){
                        idx[j]=idx[u];
                        pos[j]=pos[u];
                        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]);
                        pos[tmp[j]]=j-p;
                        cycle[tmp[j]]=1;
                    }
                    for (int j:tmp){
                        idx[j]=id;
                        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<Q;i++){
        res=0;
        for (int j=0;j<id;j++)
            for (int k:ve[j])
                dfs(k,G[i]-1);
        answer(res);
    }
}

Compilation message

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

Subtask #1
49.0 / 49.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 5 ms 27268 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 5 ms 27224 KB Output is correct
5 Correct 5 ms 27224 KB Output is correct
6 Correct 6 ms 27484 KB Output is correct
7 Correct 5 ms 27224 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 7 ms 27484 KB Output is correct
10 Correct 5 ms 27228 KB Output is correct
11 Correct 13 ms 28248 KB Output is correct
12 Correct 32 ms 28496 KB Output is correct
13 Correct 24 ms 31428 KB Output is correct
14 Correct 90 ms 37600 KB Output is correct
15 Correct 122 ms 38228 KB Output is correct
16 Correct 76 ms 36176 KB Output is correct
17 Correct 82 ms 36664 KB Output is correct
18 Correct 26 ms 30296 KB Output is correct
19 Correct 120 ms 37600 KB Output is correct
20 Correct 111 ms 38032 KB Output is correct
21 Correct 67 ms 37232 KB Output is correct
22 Correct 94 ms 35740 KB Output is correct
23 Correct 105 ms 38088 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 5 ms 27268 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 5 ms 27224 KB Output is correct
5 Correct 5 ms 27224 KB Output is correct
6 Correct 6 ms 27484 KB Output is correct
7 Correct 5 ms 27224 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 7 ms 27484 KB Output is correct
10 Correct 5 ms 27228 KB Output is correct
11 Correct 13 ms 28248 KB Output is correct
12 Correct 32 ms 28496 KB Output is correct
13 Correct 24 ms 31428 KB Output is correct
14 Correct 90 ms 37600 KB Output is correct
15 Correct 122 ms 38228 KB Output is correct
16 Correct 76 ms 36176 KB Output is correct
17 Correct 82 ms 36664 KB Output is correct
18 Correct 26 ms 30296 KB Output is correct
19 Correct 120 ms 37600 KB Output is correct
20 Correct 111 ms 38032 KB Output is correct
21 Correct 67 ms 37232 KB Output is correct
22 Correct 94 ms 35740 KB Output is correct
23 Correct 105 ms 38088 KB Output is correct
24 Correct 8 ms 27224 KB Output is correct
25 Correct 1336 ms 28432 KB Output is correct
26 Execution timed out 5073 ms 28660 KB Time limit exceeded
27 Halted 0 ms 0 KB -