oj.uz

Submission #1086736

# Submission time Handle Problem Language Result Execution time Memory
1086736 2024-09-11T11:34:44 Z asli_bg Tropical Garden (IOI11_garden) C++11
69 / 100
 191 ms 195920 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 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 38 ms 78448 KB Output is correct
2 Correct 36 ms 78620 KB Output is correct
3 Correct 35 ms 78676 KB Output is correct
4 Correct 34 ms 77780 KB Output is correct
5 Correct 37 ms 77904 KB Output is correct
6 Correct 35 ms 78632 KB Output is correct
7 Correct 37 ms 77908 KB Output is correct
8 Correct 35 ms 78684 KB Output is correct
9 Correct 37 ms 78940 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 78448 KB Output is correct
2 Correct 36 ms 78620 KB Output is correct
3 Correct 35 ms 78676 KB Output is correct
4 Correct 34 ms 77780 KB Output is correct
5 Correct 37 ms 77904 KB Output is correct
6 Correct 35 ms 78632 KB Output is correct
7 Correct 37 ms 77908 KB Output is correct
8 Correct 35 ms 78684 KB Output is correct
9 Correct 37 ms 78940 KB Output is correct
10 Correct 34 ms 77912 KB Output is correct
11 Correct 53 ms 95572 KB Output is correct
12 Correct 75 ms 108112 KB Output is correct
13 Correct 116 ms 144724 KB Output is correct
14 Correct 171 ms 184912 KB Output is correct
15 Correct 175 ms 186016 KB Output is correct
16 Correct 150 ms 151856 KB Output is correct
17 Correct 128 ms 140628 KB Output is correct
18 Correct 75 ms 108164 KB Output is correct
19 Correct 174 ms 184860 KB Output is correct
20 Correct 172 ms 185952 KB Output is correct
21 Correct 140 ms 151896 KB Output is correct
22 Correct 126 ms 140628 KB Output is correct
23 Correct 191 ms 195920 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 78448 KB Output is correct
2 Correct 36 ms 78620 KB Output is correct
3 Correct 35 ms 78676 KB Output is correct
4 Correct 34 ms 77780 KB Output is correct
5 Correct 37 ms 77904 KB Output is correct
6 Correct 35 ms 78632 KB Output is correct
7 Correct 37 ms 77908 KB Output is correct
8 Correct 35 ms 78684 KB Output is correct
9 Correct 37 ms 78940 KB Output is correct
10 Correct 34 ms 77912 KB Output is correct
11 Correct 53 ms 95572 KB Output is correct
12 Correct 75 ms 108112 KB Output is correct
13 Correct 116 ms 144724 KB Output is correct
14 Correct 171 ms 184912 KB Output is correct
15 Correct 175 ms 186016 KB Output is correct
16 Correct 150 ms 151856 KB Output is correct
17 Correct 128 ms 140628 KB Output is correct
18 Correct 75 ms 108164 KB Output is correct
19 Correct 174 ms 184860 KB Output is correct
20 Correct 172 ms 185952 KB Output is correct
21 Correct 140 ms 151896 KB Output is correct
22 Correct 126 ms 140628 KB Output is correct
23 Correct 191 ms 195920 KB Output is correct
24 Incorrect 37 ms 77912 KB Output isn't correct
25 Halted 0 ms 0 KB -