oj.uz

Submission #1086732

# Submission time Handle Problem Language Result Execution time Memory
1086732 2024-09-11T11:16:09 Z asli_bg Tropical Garden (IOI11_garden) C++11
49 / 100
 146 ms 152044 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((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 29 ms 64336 KB Output is correct
2 Correct 28 ms 64332 KB Output is correct
3 Correct 29 ms 64340 KB Output is correct
4 Correct 29 ms 63832 KB Output is correct
5 Correct 28 ms 63832 KB Output is correct
6 Correct 29 ms 64344 KB Output is correct
7 Correct 28 ms 63836 KB Output is correct
8 Correct 28 ms 64288 KB Output is correct
9 Correct 28 ms 64600 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64336 KB Output is correct
2 Correct 28 ms 64332 KB Output is correct
3 Correct 29 ms 64340 KB Output is correct
4 Correct 29 ms 63832 KB Output is correct
5 Correct 28 ms 63832 KB Output is correct
6 Correct 29 ms 64344 KB Output is correct
7 Correct 28 ms 63836 KB Output is correct
8 Correct 28 ms 64288 KB Output is correct
9 Correct 28 ms 64600 KB Output is correct
10 Correct 27 ms 63828 KB Output is correct
11 Correct 41 ms 78416 KB Output is correct
12 Correct 60 ms 88780 KB Output is correct
13 Correct 96 ms 118748 KB Output is correct
14 Incorrect 146 ms 152044 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 64336 KB Output is correct
2 Correct 28 ms 64332 KB Output is correct
3 Correct 29 ms 64340 KB Output is correct
4 Correct 29 ms 63832 KB Output is correct
5 Correct 28 ms 63832 KB Output is correct
6 Correct 29 ms 64344 KB Output is correct
7 Correct 28 ms 63836 KB Output is correct
8 Correct 28 ms 64288 KB Output is correct
9 Correct 28 ms 64600 KB Output is correct
10 Correct 27 ms 63828 KB Output is correct
11 Correct 41 ms 78416 KB Output is correct
12 Correct 60 ms 88780 KB Output is correct
13 Correct 96 ms 118748 KB Output is correct
14 Incorrect 146 ms 152044 KB Output isn't correct
15 Halted 0 ms 0 KB -