Submission #667117

#	Time	Username	Problem	Language	Result	Execution time	Memory
667117		ansgar	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	124 ms	262144 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vb vector<bool>
#define vc vector<char>
#define vvc vector<vc>
#define vvb vector<vb>
#define si set<int>
#define mii map<int,int>

const int mod=1e9+7;
const int N=2e5+1;
const int LN=INT_MAX/10;
vi T;
struct com{
    bool operator()(pair<pii,int>& a,pair<pii,int>& b){
        return a.second>b.second;
    }
};
struct co{
    bool operator()(pii& a,pii& b){
        return a.second>b.second;
    }
};
vvpii G;
void dfs(int u,int p=0){
    if(G[u].size()==1){
        T[u]=0;
        return;
    }
    vi sol;
    for(auto x : G[u]){
        int v=x.first;
        int w=x.second;
        if(v==p)continue;
        dfs(v,u);
        sol.push_back(T[v]+w);
    }
    sort(sol.begin(),sol.end());
    sol.push_back(LN);
    T[u]=sol[1];
}
int travel_plan(int n,int m,int R[][2],int L[],int k,int P[]){
    G=vvpii (n);
        //cerr<<"b";
        T=vi(n,0);
    for(int i=0;i<m;i++){
        //cerr<<i<<endl;
        //cerr<<R[i][0]<<endl;
        G[R[i][0]].push_back({R[i][1],L[i]});
        G[R[i][1]].push_back({R[i][0],L[i]});
    }
    dfs(0);
    return T[0];
}
/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    int R[m][2];
    int L[m];
    for(int i=0;i<m;i++)cin>>R[i][0]>>R[i][1]>>L[i];
    int P[k];
    for(int i=0;i<k;i++)cin>>P[i];
    //cerr<<1;
    cout<<travel_plan(n,m,R,L,k,P);
}*/

• Subtask 1: 46 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11