제출 #1350366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1350366		ozner77	LOSTIKS (INOI20_lostiks)	C++20	0 / 100	1 ms	432 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> K;
map<ll,map<ll,ll>> M;
vector<vector<ll>> UWU;
vector<vector<ll>> adj;
vector<ll> camino;
vector<ll> respuesta;
map<ll,ll> puerta;
vector<bool> visitado;
void meter(ll cur){
    if(visitado[cur]){
        return;
    }
    visitado[cur]=true;
    for(int i=0;i<UWU[cur].size();i++){
        meter(UWU[cur][i]);
    }
    respuesta.push_back(cur);
    respuesta.push_back(puerta[cur]);
}
bool dfs2(ll cur,ll p,ll obj){
    if(cur==obj){
        camino.push_back(cur);
        return true;
    }
    for(auto x:adj[cur]){
        if(x!=p){
            bool uwu=dfs2(x,cur,obj);
            if(uwu){
                camino.push_back(cur);
                return true;
            }
        }
    }
}
void dfs(ll cur, ll p,vector<ll> keys){
    if(M[p][cur]!=-1){
        puerta[M[p][cur]]=p;
        keys.push_back(M[p][cur]);
    }
    if(K[cur]==1){
        UWU[cur]=keys;
    }
    for(auto x:adj[cur]){
        if(x!=p){
            dfs(x,cur,keys);
        }
    } 
}
int main(){
    ll n;
    cin>>n;
    ll s,t;
    cin>>s>>t;
    s--;
    t--;
    UWU.resize(n);
    adj.resize(n);
    K.resize(n);
    visitado.resize(n);
    for(int i=0;i<n-1;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        c--;
        adj[a].push_back(b);
        adj[b].push_back(a);
        M[a][b]=c;
        M[b][a]=c;
        K[c]=1;     
    }
    for(int i=0;i<n;i++){
        M[i][i]=-1;
    }
    dfs(s,s,{});
    bool jajajaj=dfs2(s,-1,t);
    reverse(camino.begin(),camino.end());
    ll actu=s;
    ll ans=0; 
    respuesta.push_back(s);
    for(int i=1;i<camino.size();i++){
        if(M[actu][camino[i]]!=-1){
            meter(M[actu][camino[i]]);
        }
        actu=camino[i];
    }
    respuesta.push_back(t);
    for(int i=1;i<respuesta.size();i++){
        ans+=respuesta[i]-respuesta[i-1];
    }
    cout<<ans;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'bool dfs2(long long int, long long int, long long int)':
Main.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
   37 | }
      | ^

• Subtask 1: 0 / 23
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41