oj.uz

Submission #1086738

# Submission time Handle Problem Language Result Execution time Memory
1086738 2024-09-11T11:40:27 Z asli_bg Tropical Garden (IOI11_garden) C++11
69 / 100
 5000 ms 142160 KB 
#include<bits/stdc++.h>
using namespace std;

#include "garden.h"
#include "gardenlib.h"

//#define int long long
 
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
 
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
 
#define sp <<' '<<
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
 
#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;}
#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
 
#define carp(x,y) (((x)%mod)*((y)%mod))%mod
#define topla(x,y) (((x)%mod)+((y)%mod))%mod
 
const int MAXN=2e5+4;
const int MAXK=31;
 
#define mid (l+r)/2
#define endl '\n'

int n,m,p;
vii adj[MAXN];
int suc[MAXN][MAXK][3];
int cik[MAXN][MAXK][3];

void calc(){
    FORE(k,1,MAXK){
        FORE(nd,1,n+1){
            if(suc[nd][k-1][1]!=-1){ //1.routeu izleyerek k-1 adım gidiliyorsa
                int bir=suc[nd][k-1][1];
                suc[nd][k][1]=suc[bir][k-1][cik[nd][k-1][1]];//min edge i kullan da gel
                cik[nd][k][1]=cik[bir][k-1][cik[nd][k-1][1]];
            }

            
            if(suc[nd][k-1][2]!=-1){
                int bir=suc[nd][k-1][2];
                suc[nd][k][2]=suc[bir][k-1][cik[nd][k-1][2]];//min edge i kullan da gel
                cik[nd][k][2]=cik[bir][k-1][cik[nd][k-1][2]];
            }
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n=N;
    m=M;
    p=P;
    p++;
    memset(suc, -1, sizeof suc);
    FORE(i,1,m+1){
        int from=R[i-1][0];
        int to=R[i-1][1];
        from++;to++;
        adj[from].pb({i-1,to});
        adj[to].pb({i-1,from});
    }

    FORE(i,1,n+1){
        sort(all(adj[i]));
        while(adj[i].size()>2) adj[i].pop_back();
        
        if(adj[i].size()>=1){
            int kom=adj[i][0].se;
            //1.routu izle
            suc[i][0][1]=kom;
            if(adj[kom][0].se==i and adj[kom].size()>1){
                cik[i][0][1]=2;
                //successor i'nin hangi nodeundan devam edicem
            }
            else{
                cik[i][0][1]=1;
            }
        }

        if(adj[i].size()>=2){ //2.bir route varsa
            //2.routu izle
            int kom=adj[i][1].se;
            suc[i][0][2]=kom;
            if(adj[kom][0].se==i and adj[kom].size()>1){
                cik[i][0][2]=2;
            }
            else{
                cik[i][0][2]=1;
            }
        }

    }

    //calculate successor of each node
    calc();

    int q=Q;
    vi qq, cc;
    FOR(i,q){
        int deg=G[i];
        qq.pb(deg);
        cc.pb(deg);
    }

    sort(all(qq));

    vi cur(n+1);
    map<int,int> cev;
    FORE(i,1,n+1) cur[i]=i;

    int once=0;
    vi rt(n+1,1);
    for(auto ell:qq){ 
        int el=ell;
        el-=once;
        if(el==0) continue;
        FOR(i,MAXK){
            if(el&(1<<i)){
                FORE(nd,1,n+1){
                    if(cur[nd]==-1) continue;
                    int node=cur[nd];
                    cur[nd]=suc[node][i][rt[nd]];
                    rt[nd]=cik[node][i][rt[nd]];
                }
            }

            /*FORE(nd,1,n+1){
                DEBUG(nd);
                DEBUG(cur[nd]);
            }
            cout<<endl;*/
        }

        FORE(nd,1,n+1){
            if(cur[nd]==p) cev[ell]++;
        }

        once+=el;
    }

    for(auto el:cc){
        answer(cev[el]);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78160 KB Output is correct
2 Correct 34 ms 78108 KB Output is correct
3 Correct 32 ms 78168 KB Output is correct
4 Correct 31 ms 77904 KB Output is correct
5 Correct 32 ms 77864 KB Output is correct
6 Correct 34 ms 78164 KB Output is correct
7 Correct 34 ms 77908 KB Output is correct
8 Correct 36 ms 78160 KB Output is correct
9 Correct 42 ms 78676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78160 KB Output is correct
2 Correct 34 ms 78108 KB Output is correct
3 Correct 32 ms 78168 KB Output is correct
4 Correct 31 ms 77904 KB Output is correct
5 Correct 32 ms 77864 KB Output is correct
6 Correct 34 ms 78164 KB Output is correct
7 Correct 34 ms 77908 KB Output is correct
8 Correct 36 ms 78160 KB Output is correct
9 Correct 42 ms 78676 KB Output is correct
10 Correct 31 ms 77912 KB Output is correct
11 Correct 50 ms 87376 KB Output is correct
12 Correct 60 ms 94548 KB Output is correct
13 Correct 105 ms 113744 KB Output is correct
14 Correct 146 ms 136016 KB Output is correct
15 Correct 144 ms 137052 KB Output is correct
16 Correct 111 ms 119124 KB Output is correct
17 Correct 99 ms 113488 KB Output is correct
18 Correct 64 ms 94548 KB Output is correct
19 Correct 140 ms 136272 KB Output is correct
20 Correct 147 ms 137044 KB Output is correct
21 Correct 116 ms 119120 KB Output is correct
22 Correct 104 ms 113248 KB Output is correct
23 Correct 156 ms 142160 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78160 KB Output is correct
2 Correct 34 ms 78108 KB Output is correct
3 Correct 32 ms 78168 KB Output is correct
4 Correct 31 ms 77904 KB Output is correct
5 Correct 32 ms 77864 KB Output is correct
6 Correct 34 ms 78164 KB Output is correct
7 Correct 34 ms 77908 KB Output is correct
8 Correct 36 ms 78160 KB Output is correct
9 Correct 42 ms 78676 KB Output is correct
10 Correct 31 ms 77912 KB Output is correct
11 Correct 50 ms 87376 KB Output is correct
12 Correct 60 ms 94548 KB Output is correct
13 Correct 105 ms 113744 KB Output is correct
14 Correct 146 ms 136016 KB Output is correct
15 Correct 144 ms 137052 KB Output is correct
16 Correct 111 ms 119124 KB Output is correct
17 Correct 99 ms 113488 KB Output is correct
18 Correct 64 ms 94548 KB Output is correct
19 Correct 140 ms 136272 KB Output is correct
20 Correct 147 ms 137044 KB Output is correct
21 Correct 116 ms 119120 KB Output is correct
22 Correct 104 ms 113248 KB Output is correct
23 Correct 156 ms 142160 KB Output is correct
24 Correct 40 ms 77904 KB Output is correct
25 Correct 674 ms 87636 KB Output is correct
26 Correct 844 ms 94808 KB Output is correct
27 Execution timed out 5038 ms 114000 KB Time limit exceeded
28 Halted 0 ms 0 KB -