Submission #133529

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
133529	2019-07-21T03:44:41 Z	Utaha	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())

const ll maxn=1005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

bool vis[maxn];
vector<pll> edge[maxn];
vector<int> cmp;
int par[maxn];
int sz[maxn];
ll dis[maxn];
int c[maxn];
int anc[maxn];

vector<pii> data[maxn];
int rec[1000005];

void CD(int u,int req){
    cmp.clear();
    cmp.pb(u);
    vis[u]=1;
    par[u]=-1;
    {
        int pt=0;
        while(pt<SZ(cmp)){
            int cur=cmp[pt++];
            for(pll v:edge[cur]) if(!vis[v.F]){
                vis[v.F]=1;
                cmp.pb(v.F);
                par[v.F]=cur;
            }
        }
    }
    for(int i:cmp) vis[i]=0;
    reverse(ALL(cmp));
    int centroid=-1;
    for(int u:cmp){
        sz[u]=1;
        bool f=1;
        for(pii v:edge[u]) if(!vis[v.F]&&v.F!=par[u]){
            sz[u]+=sz[v.F];
            if(sz[v.F]+sz[v.F]>SZ(cmp)) f=0;
        }
        if(sz[u]+sz[u]<SZ(cmp)) f=0;
        if(f) centroid=u;
    }
    // for(int i:cmp) cout<<i<<' ';
    // cout<<'\n';
    // for(int i:cmp) cout<<sz[i]<<' ';
    // cout<<'\n';
    cmp.clear();
    cmp.pb(centroid);
    vis[centroid]=1;
    par[centroid]=-1;
    dis[centroid]=0;
    c[centroid]=0;
    {
        int pt=0;
        while(pt<SZ(cmp)){
            int cur=cmp[pt++];
            for(pll v:edge[cur]) if(!vis[v.F]){
                vis[v.F]=1;
                cmp.pb(v.F);
                par[v.F]=v.S;
                dis[v.F]=dis[u]+v.F;
                c[v.F]=c[u]+1;
                if(dis[v.F]==req) ans=min(ans,c[v.F]);

                if(cur==centroid){
                    anc[v.F]=v.F;
                    data[v.F].clear();
                }
                else anc[v.F]=anc[cur];
                data[anc[v.F]].pb(MP(dis[v.F],c[v.F]));
            }
        }
    }

    for(pll v:edge[centroid]) if(!vis[v.F]){
        for(auto i:data[v.F]) if(i.F<=req){
            if(rec[req-i.F]!=0){
                ans=min(ans,rec[req-i.F]+i.S);
            }
        }
        for(auto i:data[v.F]) if(i.F<=req){
            rec[i.F]=(rec[i.F]==0)?i.S:min(rec[i.F],i.S);
        }
    }

    for(int i:cmp) if(dis[i]<=req){
        rec[dis[i]]=0;
    }
    for(int i:cmp) vis[i]=0;
    vis[centroid]=1;

    // cout<<"center: "<<centroid<<'\n';
    // for(int i:cmp) cout<<i<<' ';
    // cout<<'\n';
    
    for(auto v:edge[centroid]) if(!vis[v.F]) CD(v.F,req);
}

int best_path(int n,int k,int e[][2],int l[]){
    memset(rec,0,sizeof rec);
    REP(i,n-1){
        edge[e[i][0]].pb(MP(e[i][1],l[i]));
        edge[e[i][1]].pb(MP(e[i][0],l[i]));
    }
    CD(0,k);

    if(ans==INF) ans=-1;
    return ans;
}
/*
int e[][2]={{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}};
int l[]={3,4,5,4,6,3,2,5,6,7};
int main(){
    cout<<best_path(11,12,e,l);
}
*/

Compilation message

race.cpp: In function 'void CD(int, int)':
race.cpp:89:35: error: 'ans' was not declared in this scope
                 if(dis[v.F]==req) ans=min(ans,c[v.F]);
                                   ^~~
race.cpp:89:35: note: suggested alternative: 'anc'
                 if(dis[v.F]==req) ans=min(ans,c[v.F]);
                                   ^~~
                                   anc
race.cpp:104:17: error: 'ans' was not declared in this scope
                 ans=min(ans,rec[req-i.F]+i.S);
                 ^~~
race.cpp:104:17: note: suggested alternative: 'anc'
                 ans=min(ans,rec[req-i.F]+i.S);
                 ^~~
                 anc
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:133:8: error: 'ans' was not declared in this scope
     if(ans==INF) ans=-1;
        ^~~
race.cpp:133:8: note: suggested alternative: 'anc'
     if(ans==INF) ans=-1;
        ^~~
        anc
race.cpp:134:12: error: 'ans' was not declared in this scope
     return ans;
            ^~~
race.cpp:134:12: note: suggested alternative: 'anc'
     return ans;
            ^~~
            anc