oj.uz

Submission #1086734

# Submission time Handle Problem Language Result Execution time Memory
1086734 2024-09-11T11:24:19 Z asli_bg Tropical Garden (IOI11_garden) C++11
49 / 100
 147 ms 150400 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=25;
 
#define mid (l+r)/2
#define endl '\n'

int n,m,p;
vii adj[MAXN];
int suc[MAXN][MAXK][3];
int gir[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]];
                gir[nd][k][1]=2;
            }

            
            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]];
                gir[nd][k][2]=1;
            }
        }
    }
}

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;
            gir[i][0][1]=2; // maxla gir
            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;
            gir[i][0][2]=1; //minle gir
            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;
        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 29 ms 64132 KB Output is correct
2 Correct 28 ms 64336 KB Output is correct
3 Correct 28 ms 64340 KB Output is correct
4 Correct 26 ms 63836 KB Output is correct
5 Correct 25 ms 63836 KB Output is correct
6 Correct 27 ms 64384 KB Output is correct
7 Correct 26 ms 63824 KB Output is correct
8 Correct 28 ms 64336 KB Output is correct
9 Correct 27 ms 64744 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64132 KB Output is correct
2 Correct 28 ms 64336 KB Output is correct
3 Correct 28 ms 64340 KB Output is correct
4 Correct 26 ms 63836 KB Output is correct
5 Correct 25 ms 63836 KB Output is correct
6 Correct 27 ms 64384 KB Output is correct
7 Correct 26 ms 63824 KB Output is correct
8 Correct 28 ms 64336 KB Output is correct
9 Correct 27 ms 64744 KB Output is correct
10 Correct 25 ms 63824 KB Output is correct
11 Correct 43 ms 78164 KB Output is correct
12 Correct 58 ms 88316 KB Output is correct
13 Correct 96 ms 117620 KB Output is correct
14 Incorrect 147 ms 150400 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64132 KB Output is correct
2 Correct 28 ms 64336 KB Output is correct
3 Correct 28 ms 64340 KB Output is correct
4 Correct 26 ms 63836 KB Output is correct
5 Correct 25 ms 63836 KB Output is correct
6 Correct 27 ms 64384 KB Output is correct
7 Correct 26 ms 63824 KB Output is correct
8 Correct 28 ms 64336 KB Output is correct
9 Correct 27 ms 64744 KB Output is correct
10 Correct 25 ms 63824 KB Output is correct
11 Correct 43 ms 78164 KB Output is correct
12 Correct 58 ms 88316 KB Output is correct
13 Correct 96 ms 117620 KB Output is correct
14 Incorrect 147 ms 150400 KB Output isn't correct
15 Halted 0 ms 0 KB -