oj.uz

Submission #1086787

# Submission time Handle Problem Language Result Execution time Memory
1086787 2024-09-11T13:25:03 Z asli_bg Tropical Garden (IOI11_garden) C++11
69 / 100
 5000 ms 119368 KB 
#pragma GCC optimize ("O3,unroll-loops")

#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 24 ms 56912 KB Output is correct
2 Correct 31 ms 57172 KB Output is correct
3 Correct 26 ms 57180 KB Output is correct
4 Correct 24 ms 56620 KB Output is correct
5 Correct 25 ms 56664 KB Output is correct
6 Correct 26 ms 57176 KB Output is correct
7 Correct 25 ms 56668 KB Output is correct
8 Correct 25 ms 57188 KB Output is correct
9 Correct 26 ms 57432 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 56912 KB Output is correct
2 Correct 31 ms 57172 KB Output is correct
3 Correct 26 ms 57180 KB Output is correct
4 Correct 24 ms 56620 KB Output is correct
5 Correct 25 ms 56664 KB Output is correct
6 Correct 26 ms 57176 KB Output is correct
7 Correct 25 ms 56668 KB Output is correct
8 Correct 25 ms 57188 KB Output is correct
9 Correct 26 ms 57432 KB Output is correct
10 Correct 26 ms 56668 KB Output is correct
11 Correct 38 ms 65884 KB Output is correct
12 Correct 54 ms 73108 KB Output is correct
13 Correct 85 ms 91788 KB Output is correct
14 Correct 122 ms 113432 KB Output is correct
15 Correct 124 ms 114248 KB Output is correct
16 Correct 105 ms 96956 KB Output is correct
17 Correct 89 ms 91452 KB Output is correct
18 Correct 51 ms 73048 KB Output is correct
19 Correct 125 ms 113236 KB Output is correct
20 Correct 125 ms 114256 KB Output is correct
21 Correct 98 ms 96844 KB Output is correct
22 Correct 91 ms 91220 KB Output is correct
23 Correct 138 ms 119368 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 56912 KB Output is correct
2 Correct 31 ms 57172 KB Output is correct
3 Correct 26 ms 57180 KB Output is correct
4 Correct 24 ms 56620 KB Output is correct
5 Correct 25 ms 56664 KB Output is correct
6 Correct 26 ms 57176 KB Output is correct
7 Correct 25 ms 56668 KB Output is correct
8 Correct 25 ms 57188 KB Output is correct
9 Correct 26 ms 57432 KB Output is correct
10 Correct 26 ms 56668 KB Output is correct
11 Correct 38 ms 65884 KB Output is correct
12 Correct 54 ms 73108 KB Output is correct
13 Correct 85 ms 91788 KB Output is correct
14 Correct 122 ms 113432 KB Output is correct
15 Correct 124 ms 114248 KB Output is correct
16 Correct 105 ms 96956 KB Output is correct
17 Correct 89 ms 91452 KB Output is correct
18 Correct 51 ms 73048 KB Output is correct
19 Correct 125 ms 113236 KB Output is correct
20 Correct 125 ms 114256 KB Output is correct
21 Correct 98 ms 96844 KB Output is correct
22 Correct 91 ms 91220 KB Output is correct
23 Correct 138 ms 119368 KB Output is correct
24 Correct 26 ms 56924 KB Output is correct
25 Correct 574 ms 66132 KB Output is correct
26 Correct 853 ms 73044 KB Output is correct
27 Execution timed out 5034 ms 91856 KB Time limit exceeded
28 Halted 0 ms 0 KB -