Submission #894901

#	Time	Username	Problem	Language	Result	Execution time	Memory
894901		n0sk1ll	Cyberland (APIO23_cyberland)	C++17	Compilation error	0 ms	0 KiB

cyberland

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//const int mod=1'000'000'000;







//Note to self: Check for overflow

int k,n;
vector<vector<pii>> g(100005);
double dub[2][102][100005]; //min depth to each version of every node
bool vis[2][102][100005];

bool vist[100005]; //temporary
void dfs(int p)
{
    if (vist[p]) return;
    vist[p]=true;
    for (auto it : g[p]) dfs(it.xx);
}

void add_edge(int u, int v, int w)
{
    g[u].push_back({v,w});
}

double solve(int N, int m, int K, int H, std::vector<int> u, std::vector<int> v, std::vector<int> w, std::vector<int> arr)
{
    n=N;
    bool hyper=false;
    k=min(K,70);
    ff(i,0,n) g[i].clear();
    ff(stat,0,2) fff(kolko,0,k) ff(i,0,n) dub[stat][kolko][i]=0,vis[stat][kolko][i]=false;
    ff(i,0,n) vist[i]=false;
    ff(i,0,m)
    {
        if (u[i]==H) add_edge(v[i],u[i],w[i]);
        else if (v[i]==H) add_edge(u[i],v[i],w[i]);
        else add_edge(u[i],v[i],w[i]),add_edge(v[i],u[i],w[i]);
    }

    dfs(0);
    if (!vist[H]) return -1;
    vector<int> sources={0};
    ff(i,1,n) if (vist[i] && arr[i]==0) sources.push_back(i);

    #define typ pair<double,pair<int,bool>>
    priority_queue<typ,vector<typ>,greater<typ>> pq[102];
    for (auto it : sources) pq[0].push({0,{it,false}});

    fff(kolko,0,k) while (!pq[kolko].empty())
    {
        double d=pq[kolko].top().xx;
        int p=pq[kolko].top().yy.xx;
        bool stat=pq[kolko].top().yy.yy;
        pq[kolko].pop();
        if (vis[stat][kolko][p]) continue;
        vis[stat][kolko][p]=true;
        dub[stat][kolko][p]=d;

        for (auto it : g[p]) pq[kolko].push({d+it.yy,{it.xx,false}});
        if (arr[p]==2 && !stat) pq[kolko+1].push({d/2,{p,true}});
    }

    double ans=1e18;
    ff(stat,0,2) fff(i,0,k) if (vis[stat][i][H]) ans=min(ans,dub[stat][i][H]);
    return ans;
}

main()
{
    FAST;

    cout<<solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1})<<endl;
}

//Note to self: Check for overflow

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:59:10: warning: unused variable 'hyper' [-Wunused-variable]
   59 |     bool hyper=false;
      |          ^~~~~
cyberland.cpp: At global scope:
cyberland.cpp:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main()
      | ^~~~
/usr/bin/ld: /tmp/ccOPZQBw.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc0f5Acw.o:cyberland.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status