oj.uz

Submission #1086739

# Submission time Handle Problem Language Result Execution time Memory
1086739 2024-09-11T11:42:28 Z asli_bg Tropical Garden (IOI11_garden) C++11
69 / 100
 5000 ms 140368 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((1<<i)>el) break;
            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 35 ms 78160 KB Output is correct
2 Correct 42 ms 78164 KB Output is correct
3 Correct 36 ms 78168 KB Output is correct
4 Correct 35 ms 77852 KB Output is correct
5 Correct 33 ms 77916 KB Output is correct
6 Correct 36 ms 78164 KB Output is correct
7 Correct 33 ms 77832 KB Output is correct
8 Correct 34 ms 78184 KB Output is correct
9 Correct 36 ms 78408 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 78160 KB Output is correct
2 Correct 42 ms 78164 KB Output is correct
3 Correct 36 ms 78168 KB Output is correct
4 Correct 35 ms 77852 KB Output is correct
5 Correct 33 ms 77916 KB Output is correct
6 Correct 36 ms 78164 KB Output is correct
7 Correct 33 ms 77832 KB Output is correct
8 Correct 34 ms 78184 KB Output is correct
9 Correct 36 ms 78408 KB Output is correct
10 Correct 44 ms 77888 KB Output is correct
11 Correct 49 ms 87124 KB Output is correct
12 Correct 61 ms 94032 KB Output is correct
13 Correct 95 ms 112728 KB Output is correct
14 Correct 142 ms 134484 KB Output is correct
15 Correct 142 ms 135092 KB Output is correct
16 Correct 114 ms 117584 KB Output is correct
17 Correct 103 ms 111792 KB Output is correct
18 Correct 65 ms 94036 KB Output is correct
19 Correct 150 ms 134376 KB Output is correct
20 Correct 150 ms 135248 KB Output is correct
21 Correct 115 ms 117584 KB Output is correct
22 Correct 108 ms 111696 KB Output is correct
23 Correct 157 ms 140368 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 78160 KB Output is correct
2 Correct 42 ms 78164 KB Output is correct
3 Correct 36 ms 78168 KB Output is correct
4 Correct 35 ms 77852 KB Output is correct
5 Correct 33 ms 77916 KB Output is correct
6 Correct 36 ms 78164 KB Output is correct
7 Correct 33 ms 77832 KB Output is correct
8 Correct 34 ms 78184 KB Output is correct
9 Correct 36 ms 78408 KB Output is correct
10 Correct 44 ms 77888 KB Output is correct
11 Correct 49 ms 87124 KB Output is correct
12 Correct 61 ms 94032 KB Output is correct
13 Correct 95 ms 112728 KB Output is correct
14 Correct 142 ms 134484 KB Output is correct
15 Correct 142 ms 135092 KB Output is correct
16 Correct 114 ms 117584 KB Output is correct
17 Correct 103 ms 111792 KB Output is correct
18 Correct 65 ms 94036 KB Output is correct
19 Correct 150 ms 134376 KB Output is correct
20 Correct 150 ms 135248 KB Output is correct
21 Correct 115 ms 117584 KB Output is correct
22 Correct 108 ms 111696 KB Output is correct
23 Correct 157 ms 140368 KB Output is correct
24 Correct 35 ms 77904 KB Output is correct
25 Correct 688 ms 87380 KB Output is correct
26 Correct 938 ms 94140 KB Output is correct
27 Execution timed out 5072 ms 113752 KB Time limit exceeded
28 Halted 0 ms 0 KB -