Submission #1086427

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1086427	2024-09-10T15:08:11 Z	asli_bg	Tropical Garden (IOI11_garden)	C++11	Compilation error	0 ms	0 KB

garden

#include "garden.h"
#include "gardenlib.h"

#include<bits/stdc++.h>
using namespace std;
 
#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][2];
int gir[MAXN][MAXK][2];
int cik[MAXN][MAXK][2];
//suc[n][k][b]={a,c} --> n.nodedan k kez ilerlersem a.ya ulaşırım b.edgei kullanarak

void calc(){
    FORE(k,1,MAXK){
        FORE(nd,1,n+1){
            /*
            suc[nd][k-1][1]--> 1 routeunda nd den 2^(k-1) ilerle
            bu nodedan da 2^(k-1) ilerle
            hangi routta? cikis[nd][k-1][1] routunda

            cikis[nd][k][1] neye eşit? yarıdaki nodeun k-1 gez ilerledikten sonra belirlenen routta
                            ulaştığı nodeun ciki
            */
            suc[nd][k][1]=suc[suc[nd][k-1][1]][k-1][cik[nd][k-1][1]];//min edge i kullan da gel
            cik[nd][k][1]=cik[suc[nd][k-1][1]][k-1][cik[nd][k-1][1]];
            gir[nd][k][1]=2;

            suc[nd][k][2]=suc[suc[nd][k-1][2]][k-1][cik[nd][k-1][2]];//min edge i kullan da gel
            cik[nd][k][2]=cik[suc[nd][k-1][2]][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;
    FORE(i,1,m+1){
        int from=R[i][0];
        int to=R[i][1];
        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();

        //route if i go from the min edge
        int kom=adj[i][0].se;
        int cost=adj[i][0].fi;
        suc[i][0][1]=kom; //1--> min edgele cik
        gir[i][0][1]=2; // maxla gir
        if(adj[kom][0].se==i and adj[kom].size()>1){ //komsumun min edge i de benle aramdakiyse
            cik[i][0][1]=2;//adj[kom][1].fi;
            //cik su an üstünde bulunduğum nodeun kullanılmasını
            //istediğim edgei
        }
        else{
            cik[i][0][1]=1;//adj[kom][0].fi;
        }

        if(adj[i].size()>=2){ //2.bir route varsa
            //try calculating the other edge
            kom=adj[i][1].se;
            cost=adj[i][1].fi;
            suc[i][0][2]=kom; //1-->max edgele cik
            gir[i][0][2]=1; //minle gir
            if(adj[kom][0].se==i and adj[kom].size()>1){ //komsumun min edge i de benle aramdakiyse
                cik[i][0][2]=2;//adj[kom][1].fi;
            }
            else{
                cik[i][0][2]=1;//adj[kom][0].fi;
            }
        }

    }

    //calculate successor of each node
    calc();

    int q=Q;
    vi qq, cc;
    while(q--){
        int deg;
        cin>>deg;
        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;
    for(auto el:qq){ 
        //el kadar tüm nodeları ilerlet
        el-=once;
        FORE(i,1,MAXK){
            if((1<<i)>el) break;
            if(el&(1<<i)!=0){
                FORE(nd,1,n+1){
                    cur[nd]=suc[nd][i][1];
                }
            }
        }

        FORE(nd,1,n+1){
            if(cur[nd]==p) cev[el]++;
        }
        once+=el;
    }

    for(auto el:cc){
        answer(cev[el]);
    }
}

Compilation message

garden.cpp: In function 'void count_routes(long long int, long long int, long long int, long long int (*)[2], long long int, long long int*)':
garden.cpp:83:13: warning: variable 'cost' set but not used [-Wunused-but-set-variable]
   83 |         int cost=adj[i][0].fi;
      |             ^~~~
garden.cpp:135:25: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  135 |             if(el&(1<<i)!=0){
      |                   ~~~~~~^~~
garden.cpp: In function 'void calc()':
garden.cpp:58:45: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
   58 |             suc[nd][k][2]=suc[suc[nd][k-1][2]][k-1][cik[nd][k-1][2]];//min edge i kullan da gel
      |                               ~~~~~~~~~~~~~~^
garden.cpp:58:67: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
   58 |             suc[nd][k][2]=suc[suc[nd][k-1][2]][k-1][cik[nd][k-1][2]];//min edge i kullan da gel
      |                                                     ~~~~~~~~~~~~~~^
garden.cpp:58:25: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
   58 |             suc[nd][k][2]=suc[suc[nd][k-1][2]][k-1][cik[nd][k-1][2]];//min edge i kullan da gel
      |             ~~~~~~~~~~~~^
garden.cpp:59:45: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
   59 |             cik[nd][k][2]=cik[suc[nd][k-1][2]][k-1][cik[nd][k-1][2]];
      |                               ~~~~~~~~~~~~~~^
garden.cpp:59:25: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
   59 |             cik[nd][k][2]=cik[suc[nd][k-1][2]][k-1][cik[nd][k-1][2]];
      |             ~~~~~~~~~~~~^
garden.cpp:60:25: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
   60 |             gir[nd][k][2]=1;
      |             ~~~~~~~~~~~~^
garden.cpp: In function 'void count_routes(long long int, long long int, long long int, long long int (*)[2], long long int, long long int*)':
garden.cpp:99:24: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
   99 |             suc[i][0][2]=kom; //1-->max edgele cik
      |             ~~~~~~~~~~~^
garden.cpp:100:24: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
  100 |             gir[i][0][2]=1; //minle gir
      |             ~~~~~~~~~~~^
garden.cpp:102:28: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
  102 |                 cik[i][0][2]=2;//adj[kom][1].fi;
      |                 ~~~~~~~~~~~^
garden.cpp:105:28: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
  105 |                 cik[i][0][2]=1;//adj[kom][0].fi;
      |                 ~~~~~~~~~~~^
/usr/bin/ld: /tmp/cc4B9JEY.o: in function `main':
grader.cpp:(.text.startup+0x3f): undefined reference to `count_routes(int, int, int, int (*) [2], int, int*)'
collect2: error: ld returned 1 exit status