oj.uz

Submission #852380

# Submission time Handle Problem Language Result Execution time Memory
852380 2023-09-21T16:43:00 Z abcvuitunggio Tropical Garden (IOI11_garden) C++17
100 / 100
 3930 ms 34572 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
pair <int, int> edge[150001];
int op,mx[150001],mx2[150001],nxt[300001],ch[300001],t[300001],id,cycle[300001],d[300001],cnt[300001],res,idx[300001],pos[300001];
vector <int> ke[300001],ve[300001],tmp;
void dfs(int u){
    for (int v:ke[u]){
        d[v]=d[u]+1;
        dfs(v);
    }
}
void dfs2(int u, int val){
    op++;
    if (u%2==0&&d[u]==val){
        ch[u]=1;
        return;
    }
    for (int v:ke[u])
        dfs2(v,val);
}
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]};
    memset(mx,-1,sizeof(mx));
    memset(mx2,-1,sizeof(mx2));
    for (int i=0;i<M;i++){
        auto [u,v]=edge[i];
        if (mx[u]%M<i%M){
            mx2[u]=mx[u];
            mx[u]=i;
        }
        else if (mx2[u]%M<i%M)
            mx2[u]=i;
        if (mx[v]%M<i%M){
            mx2[v]=mx[v];
            mx[v]=i;
        }
        else if (mx2[v]%M<i%M)
            mx2[v]=i;
    }
    for (int i=0;i<N;i++){
        int v=edge[mx[i]].first^edge[mx[i]].second^i;
        nxt[i*2]=v*2+1-(mx[i]!=mx[v]||mx2[v]==-1);
        if (mx2[i]==-1)
            continue;
        v=edge[mx2[i]].first^edge[mx2[i]].second^i;
        nxt[i*2+1]=v*2+1-(mx2[i]!=mx[v]||mx2[v]==-1);
    }
    t[P*2]=t[P*2+1]=1;
    for (int i=0;i<N*2;i++){
        if (i%2==1&&mx2[i/2]==-1)
            continue;
        if (!ch[i]){
            tmp.clear();
            tmp.push_back(i);
            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]);
                        cycle[tmp[j]]=1;
                        pos[tmp[j]]=j-p;
                    }
                    for (int j:tmp){
                        idx[j]=id;
                        ch[j]=2;
                    }
                    id++;
                    break;
                }
                tmp.push_back(u);
                ch[u]=1;
            }
        }
    }
    for (int i=0;i<N*2;i++){
        if (i%2==1&&mx2[i/2]==-1)
            continue;
        if (!cycle[i])
            ke[nxt[i]].push_back(i);
    }
    tmp.clear();
    for (int i=0;i<id;i++)
        for (int j:ve[i])
            dfs(j);
    memset(ch,0,sizeof(ch));
    for (int i=0;i<Q;i++){
        res=0;
        dfs2(P*2,d[P*2]+G[i]);
        dfs2(P*2+1,d[P*2+1]+G[i]);
        for (int j=0;j<N*2;j+=2){
            if (!ch[j]&&d[j]<G[i]){
                int v=ve[idx[j]][(pos[j]+G[i]-d[j])%ve[idx[j]].size()];
                ch[j]=(v==P*2||v==P*2+1);
            }
            res+=ch[j];
            ch[j]=0;
        }
        answer(res);
    }
}

Compilation message

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

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25180 KB Output is correct
2 Correct 5 ms 25220 KB Output is correct
3 Correct 6 ms 25180 KB Output is correct
4 Correct 4 ms 25180 KB Output is correct
5 Correct 4 ms 25180 KB Output is correct
6 Correct 5 ms 25180 KB Output is correct
7 Correct 4 ms 25180 KB Output is correct
8 Correct 5 ms 25204 KB Output is correct
9 Correct 7 ms 25180 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25180 KB Output is correct
2 Correct 5 ms 25220 KB Output is correct
3 Correct 6 ms 25180 KB Output is correct
4 Correct 4 ms 25180 KB Output is correct
5 Correct 4 ms 25180 KB Output is correct
6 Correct 5 ms 25180 KB Output is correct
7 Correct 4 ms 25180 KB Output is correct
8 Correct 5 ms 25204 KB Output is correct
9 Correct 7 ms 25180 KB Output is correct
10 Correct 5 ms 25180 KB Output is correct
11 Correct 11 ms 25692 KB Output is correct
12 Correct 19 ms 26504 KB Output is correct
13 Correct 22 ms 27400 KB Output is correct
14 Correct 53 ms 32644 KB Output is correct
15 Correct 56 ms 32656 KB Output is correct
16 Correct 49 ms 31056 KB Output is correct
17 Correct 43 ms 30600 KB Output is correct
18 Correct 20 ms 26712 KB Output is correct
19 Correct 57 ms 32512 KB Output is correct
20 Correct 56 ms 32592 KB Output is correct
21 Correct 47 ms 31320 KB Output is correct
22 Correct 43 ms 30544 KB Output is correct
23 Correct 53 ms 32592 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25180 KB Output is correct
2 Correct 5 ms 25220 KB Output is correct
3 Correct 6 ms 25180 KB Output is correct
4 Correct 4 ms 25180 KB Output is correct
5 Correct 4 ms 25180 KB Output is correct
6 Correct 5 ms 25180 KB Output is correct
7 Correct 4 ms 25180 KB Output is correct
8 Correct 5 ms 25204 KB Output is correct
9 Correct 7 ms 25180 KB Output is correct
10 Correct 5 ms 25180 KB Output is correct
11 Correct 11 ms 25692 KB Output is correct
12 Correct 19 ms 26504 KB Output is correct
13 Correct 22 ms 27400 KB Output is correct
14 Correct 53 ms 32644 KB Output is correct
15 Correct 56 ms 32656 KB Output is correct
16 Correct 49 ms 31056 KB Output is correct
17 Correct 43 ms 30600 KB Output is correct
18 Correct 20 ms 26712 KB Output is correct
19 Correct 57 ms 32512 KB Output is correct
20 Correct 56 ms 32592 KB Output is correct
21 Correct 47 ms 31320 KB Output is correct
22 Correct 43 ms 30544 KB Output is correct
23 Correct 53 ms 32592 KB Output is correct
24 Correct 6 ms 25176 KB Output is correct
25 Correct 249 ms 25692 KB Output is correct
26 Correct 432 ms 26960 KB Output is correct
27 Correct 1027 ms 27340 KB Output is correct
28 Correct 2242 ms 32704 KB Output is correct
29 Correct 2337 ms 32828 KB Output is correct
30 Correct 1308 ms 32792 KB Output is correct
31 Correct 1527 ms 32340 KB Output is correct
32 Correct 539 ms 27372 KB Output is correct
33 Correct 2231 ms 34388 KB Output is correct
34 Correct 2358 ms 34572 KB Output is correct
35 Correct 1386 ms 32900 KB Output is correct
36 Correct 3930 ms 32336 KB Output is correct
37 Correct 2074 ms 34484 KB Output is correct
38 Correct 1752 ms 31828 KB Output is correct