oj.uz

Submission #1086742

# Submission time Handle Problem Language Result Execution time Memory
1086742 2024-09-11T11:44:23 Z asli_bg Tropical Garden (IOI11_garden) C++11
69 / 100
 5000 ms 119064 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=150005;
const int MAXK=30;
 
#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;
        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;*/
        }

        if(el!=0){
            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 26 ms 56912 KB Output is correct
2 Correct 26 ms 57180 KB Output is correct
3 Correct 23 ms 57124 KB Output is correct
4 Correct 26 ms 56664 KB Output is correct
5 Correct 23 ms 56736 KB Output is correct
6 Correct 28 ms 57180 KB Output is correct
7 Correct 27 ms 56664 KB Output is correct
8 Correct 24 ms 57180 KB Output is correct
9 Correct 27 ms 57432 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56912 KB Output is correct
2 Correct 26 ms 57180 KB Output is correct
3 Correct 23 ms 57124 KB Output is correct
4 Correct 26 ms 56664 KB Output is correct
5 Correct 23 ms 56736 KB Output is correct
6 Correct 28 ms 57180 KB Output is correct
7 Correct 27 ms 56664 KB Output is correct
8 Correct 24 ms 57180 KB Output is correct
9 Correct 27 ms 57432 KB Output is correct
10 Correct 23 ms 56648 KB Output is correct
11 Correct 38 ms 65876 KB Output is correct
12 Correct 51 ms 73044 KB Output is correct
13 Correct 92 ms 91732 KB Output is correct
14 Correct 135 ms 113292 KB Output is correct
15 Correct 135 ms 114008 KB Output is correct
16 Correct 95 ms 96848 KB Output is correct
17 Correct 87 ms 91408 KB Output is correct
18 Correct 50 ms 73044 KB Output is correct
19 Correct 114 ms 113304 KB Output is correct
20 Correct 122 ms 114000 KB Output is correct
21 Correct 96 ms 96788 KB Output is correct
22 Correct 96 ms 91168 KB Output is correct
23 Correct 129 ms 119064 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56912 KB Output is correct
2 Correct 26 ms 57180 KB Output is correct
3 Correct 23 ms 57124 KB Output is correct
4 Correct 26 ms 56664 KB Output is correct
5 Correct 23 ms 56736 KB Output is correct
6 Correct 28 ms 57180 KB Output is correct
7 Correct 27 ms 56664 KB Output is correct
8 Correct 24 ms 57180 KB Output is correct
9 Correct 27 ms 57432 KB Output is correct
10 Correct 23 ms 56648 KB Output is correct
11 Correct 38 ms 65876 KB Output is correct
12 Correct 51 ms 73044 KB Output is correct
13 Correct 92 ms 91732 KB Output is correct
14 Correct 135 ms 113292 KB Output is correct
15 Correct 135 ms 114008 KB Output is correct
16 Correct 95 ms 96848 KB Output is correct
17 Correct 87 ms 91408 KB Output is correct
18 Correct 50 ms 73044 KB Output is correct
19 Correct 114 ms 113304 KB Output is correct
20 Correct 122 ms 114000 KB Output is correct
21 Correct 96 ms 96788 KB Output is correct
22 Correct 96 ms 91168 KB Output is correct
23 Correct 129 ms 119064 KB Output is correct
24 Correct 24 ms 56920 KB Output is correct
25 Correct 638 ms 66132 KB Output is correct
26 Correct 788 ms 73188 KB Output is correct
27 Execution timed out 5052 ms 91604 KB Time limit exceeded
28 Halted 0 ms 0 KB -