Submission #933558

#	Time	Username	Problem	Language	Result	Execution time	Memory
933558		raul2008487	Dreaming (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KiB

dreaming

#include <bits/stdc++.h>
//#include "dreaming.h"
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define ll int
#define in insert
#define pb push_back
#define vl vector<ll>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
//using namespace __gnu_pbds;
//tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> rbt;
const int sz = 2e5+5;
ll w, res;
vector<array<ll, 2>> adj[sz], dp(sz), leaf(sz);
bool used[sz];
ll node, R;
vl path;
void dfs1(ll v, ll p){
    //cout << v << endl;
    dp[v] = {0, 0};
    leaf[v] = {v, v};
    used[v] = 1; 
    for(array<ll, 2> e: adj[v]){
        if(!used[e[0]]){
            dfs1(e[0], v);
            if((dp[e[0]][0] + e[1]) > dp[v][0]){
                dp[v][1] = dp[v][0];
                leaf[v][1] = leaf[v][0];
                dp[v][0] = dp[e[0]][0] + e[1];
                leaf[v][0] = leaf[e[0]][0];
            }
            else if((dp[e[0]][0] + e[1]) > dp[v][1]){
                dp[v][1] = dp[e[0]][0] + e[1];
                leaf[v][1] = leaf[e[0]][0];
            }
        }
    }
    if((dp[v][0] + dp[v][1]) > res){
        node = v;
        res = dp[v][0] + dp[v][1];
    }
}
void getpath(ll v, ll p, ll target){
    for(array<ll, 2> e: adj[v]){
        if(e[0] != p){
            if(dp[e[0]][0] + e[1] == target){
                path.pb(e[1]);
                getpath(e[0], v, target - e[1]);
                return ;
            }
        }
    }
}
ll GetR(ll v){
    res = -1;
    dfs1(v, 0);
    //cout << endl << res << endl;
    ll l1 = leaf[node][0];
    ll l2 = leaf[node][1];
    ll bar = res / 2;
    path.clear();
    getpath(node, 0, dp[node][0]);
    reverse(all(path));
    getpath(node, 0, dp[node][1]);
    ll ret = res, cur = 0;
    R = max(R, res);
    for(auto x: path){
        cur += x;
        if(cur > bar){
            ret = min(ret, cur);
        }
        else{
            ret = min(ret, (res - cur));
        }
    }
    return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    ll n = N, m = M, i, j, k;
    w = L;
    for(i = 0; i < m; i++){
        adj[A[i] + 1].pb({B[i] + 1, T[i]});
        adj[B[i] + 1].pb({A[i] + 1, T[i]});
    }
    vl longest;
    for(i = 1; i <= n; i++){
        if(!used[i]){
            //cout << i << endl;
            longest.pb(GetR(i));
        }
    }
    sort(longest.rbegin(), longest.rend());
    if(longest.size() == 1){
        return R;
    }
    else if(longest.size() == 2){
        return max(R, longest[0] + longest[1] + w);
    }
    else{
        //cout << R << ' ' << longest[0] + longest[1] + w << ' ' << longest[1] + longest[2] + 2*w << endl; 
        return max({R, (longest[0] + longest[1] + w), (longest[1] + longest[2] + 2*w)});
    }
}
/*int main(){
    ll n = 12, m = 8, L = 2;
    ll a[8] = {0,8,2,5,5,1,1,10};
    ll b[8] = {8,2,7,11,1,3,9,6};
    ll t[8] = {4,2,4,3,7,1,5,3};
    cout <<  travelTime(n, m, L, a, b, t); 
}*/
/*

*/

Compilation message (stderr)

dreaming.cpp: In function 'int GetR(int)':
dreaming.cpp:62:8: warning: unused variable 'l1' [-Wunused-variable]
   62 |     ll l1 = leaf[node][0];
      |        ^~
dreaming.cpp:63:8: warning: unused variable 'l2' [-Wunused-variable]
   63 |     ll l2 = leaf[node][1];
      |        ^~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:83:25: warning: unused variable 'j' [-Wunused-variable]
   83 |     ll n = N, m = M, i, j, k;
      |                         ^
dreaming.cpp:83:28: warning: unused variable 'k' [-Wunused-variable]
   83 |     ll n = N, m = M, i, j, k;
      |                            ^
/usr/bin/ld: /tmp/ccXuOUl8.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status