oj.uz

답안 #1086789

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1086789 2024-09-11T13:27:18 Z asli_bg 열대 식물원 (Tropical Garden) (IOI11_garden) C++11
69 / 100
 5000 ms 117392 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];
int cur[MAXN];
int rt[MAXN];
 
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));
 
    map<int,int> cev;
    FORE(i,1,n+1) cur[i]=i;
 
    int once=0;
    FORE(i,1,n+1) rt[i]=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]];
                }
            }
        }
 
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 56924 KB Output is correct
2 Correct 25 ms 57044 KB Output is correct
3 Correct 24 ms 57176 KB Output is correct
4 Correct 23 ms 56668 KB Output is correct
5 Correct 24 ms 56664 KB Output is correct
6 Correct 26 ms 57120 KB Output is correct
7 Correct 24 ms 56656 KB Output is correct
8 Correct 25 ms 57172 KB Output is correct
9 Correct 26 ms 57428 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 56924 KB Output is correct
2 Correct 25 ms 57044 KB Output is correct
3 Correct 24 ms 57176 KB Output is correct
4 Correct 23 ms 56668 KB Output is correct
5 Correct 24 ms 56664 KB Output is correct
6 Correct 26 ms 57120 KB Output is correct
7 Correct 24 ms 56656 KB Output is correct
8 Correct 25 ms 57172 KB Output is correct
9 Correct 26 ms 57428 KB Output is correct
10 Correct 26 ms 56664 KB Output is correct
11 Correct 39 ms 65872 KB Output is correct
12 Correct 54 ms 72528 KB Output is correct
13 Correct 86 ms 90656 KB Output is correct
14 Correct 117 ms 111700 KB Output is correct
15 Correct 120 ms 112576 KB Output is correct
16 Correct 101 ms 95316 KB Output is correct
17 Correct 92 ms 89936 KB Output is correct
18 Correct 50 ms 72276 KB Output is correct
19 Correct 117 ms 111696 KB Output is correct
20 Correct 121 ms 112468 KB Output is correct
21 Correct 98 ms 95360 KB Output is correct
22 Correct 88 ms 89524 KB Output is correct
23 Correct 136 ms 117392 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 56924 KB Output is correct
2 Correct 25 ms 57044 KB Output is correct
3 Correct 24 ms 57176 KB Output is correct
4 Correct 23 ms 56668 KB Output is correct
5 Correct 24 ms 56664 KB Output is correct
6 Correct 26 ms 57120 KB Output is correct
7 Correct 24 ms 56656 KB Output is correct
8 Correct 25 ms 57172 KB Output is correct
9 Correct 26 ms 57428 KB Output is correct
10 Correct 26 ms 56664 KB Output is correct
11 Correct 39 ms 65872 KB Output is correct
12 Correct 54 ms 72528 KB Output is correct
13 Correct 86 ms 90656 KB Output is correct
14 Correct 117 ms 111700 KB Output is correct
15 Correct 120 ms 112576 KB Output is correct
16 Correct 101 ms 95316 KB Output is correct
17 Correct 92 ms 89936 KB Output is correct
18 Correct 50 ms 72276 KB Output is correct
19 Correct 117 ms 111696 KB Output is correct
20 Correct 121 ms 112468 KB Output is correct
21 Correct 98 ms 95360 KB Output is correct
22 Correct 88 ms 89524 KB Output is correct
23 Correct 136 ms 117392 KB Output is correct
24 Correct 27 ms 56816 KB Output is correct
25 Correct 628 ms 65792 KB Output is correct
26 Correct 761 ms 73104 KB Output is correct
27 Execution timed out 5053 ms 91636 KB Time limit exceeded
28 Halted 0 ms 0 KB -