제출 #805362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
805362		YassirSalama	꿈 (IOI13_dreaming)	C++17	47 / 100	96 ms	19048 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define pb push_back
#define F first
#define S second
const ll INF=1e9;
const int MAXN=1e5+100;
int n,m,l;
vector<vector<pair<int,int>>> v(MAXN);
vector<pair<ll,ll>> diameters;
bool visited[MAXN];
ll parr[MAXN];
ll depth[MAXN];
pair<ll,ll> dfs(int node,int par,ll ew=0){//depth, best node
    // if(visited[node]) return {ew,node};
    visited[node]=true;
    parr[node]=par;
    depth[node]=ew;
    // dbg(node,par,ew);
    if(v[node].size()==1&&v[node][0].F==par){
        return {ew,node};
    }
    ll ans=0;
    ll best=node;
    for(auto x:v[node]){
        if(x.F!=par){
            // dbg(x.F,node,ew,x.S);
            pair<ll,ll> p=dfs(x.F,node,ew+x.S);
            if(p.F>ans){
                ans=p.F;
                best=p.S;
            }
        }
    }
    return {ans,best};
}
ll bigdia=0;
int par[MAXN];
int f=0;
void find_diameter(int node){
    // memset(visited,false,sizeof(visited));
    pair<ll,ll> p=dfs(node,node);
    int f=p.S;
    // memset(parr,0,sizeof(parr));
    // memset(visited,false,sizeof(visited));
    p=dfs(p.S,p.S);
    // dbg(f,p.S);
    vector<ll> dia;
    while(p.S!=parr[p.S]) {
        dia.push_back(p.S);
        p.S=parr[p.S];
    }
    dia.push_back(p.S);
    reverse(all(dia));
    bigdia=p.F;
    int nodea=0;
    int nodeb=0;
    int a,b,c,e;
    ll besta=INF;
    ll bestb=INF;
    for(auto x:dia){
        a=depth[dia.back()]-depth[x];
        b=depth[x];
        if(besta>max(a,b)){
            besta=max(a,b);
            nodea=x;
        }
        par[x]=dia[0];
    }
    // if(besta==INF){
        // dbg(node);
    // }
    // assert(besta==INF);
    diameters.pb({besta,nodea});
    // dbg(besta,nodea);
    // OVL(dia," ")
    f++;
}
struct Edge{
    ll a,b;
    ll c;
    bool operator < (const Edge& other) const{
        return c<other.c;
    }
};
int find(int node){
    if(node==par[node]) return node;
    return par[node]=find(par[node]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N;
    m=M;
    l=L;
    memset(visited,false,sizeof(visited));
    for(int i=0;i<m;i++){
        v[A[i]].push_back({B[i],T[i]});
        v[B[i]].push_back({A[i],T[i]});
    }
    memset(depth,0,sizeof(depth));
    for(int i=0;i<n;i++){
        if(!visited[i]){
            find_diameter(i);
        }
    }
    vector<Edge> edges;
    int d=diameters.size();
    // cout<<d<<endl;
    bool ok=true;
    for(int i=0;i<n;i++){
        ok&=(v[i].size()<=1);
    }
    // if(ok){
        // for(int i=0;i<diameters.size();i++) dbg(diameters[i].F,diameters[i].S);
        //answer of sub4 here
        // for(int i=0;i+1<diameters.size();i++){
            // v[diameters[i].S].push_back({diameters[i+1].S,l});
            // v[diameters[i+1].S].push_back({diameters[i].S,l});

            // dbg(diameters[i].S,diameters[i+1].S,l);
        // }
        // for(int i=0;i<n;i++) {
        //     cout<<i<<" --> ";
        //     for(auto x:v[i]){
        //         cout<<" [ "<<x.F<<" ; "<<x.S<<" ] ,";
        //     }
        //     cout<<endl;
        // }
        // memset(depth,0LL,sizeof(depth));
        // dbg("START");
        // find_diameter(0);
        // dbg(f);
        // return bigdia;
    // }
    for(int i=0;i<d-1;i++){
        int nodea=diameters[i].S;
        ll besta=diameters[i].F;
        int nodeb=-1;
        ll bestb=INF;
        int j=i+1;
        // dbg(nodea,besta);
        // for(int j=i+1;j<d;j++){
            // if(bestb>diameters[j].F){
                // bestb=diameters[j].F;
                // nodeb=diameters[j].S;
            // }
            // dbg(nodea,nodeb,besta,bestb);
        edges.push_back({.a=nodea,.b=diameters[j].S,.c=besta+diameters[j].F});
        // }
        // dbg(nodea,nodeb);
    }
    sort(all(edges));
    for(auto& edge:edges){
        if(find(edge.a)==find(edge.b)) continue;
        int a=find(edge.a);
        int b=find(edge.b);
        par[b]=a;
        // dbg(edge.a,edge.b,edge.c);
        // dbg(a,b,edge.a,edge.b);
        v[edge.a].pb({edge.b,l});
        v[edge.b].pb({edge.a,l});
        f++;
    }
    // dbg(f);
    memset(depth,0LL,sizeof(depth));
    find_diameter(0);
    //working for sub4
    //here we have every element have at most one
    return bigdia;
}

#ifdef IOI

#define fail(s, x...) do { \
        fprintf(stderr, s "\n", ## x); \
        exit(1); \
    } while(0)

#define MAX_N 100000

static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];

int main() {
    int N, M, L, i;
    int res;

    FILE *f = fopen("dreaming.in", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d%d%d", &N, &M, &L);
    for (i = 0; i < M; i++)
        res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
    fclose(f);

    int answer = travelTime(N, M, L, A, B, T);
    printf("%d\n", answer);

    return 0;
}

#endif

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

dreaming.cpp: In function 'void find_diameter(int)':
dreaming.cpp:64:9: warning: unused variable 'nodeb' [-Wunused-variable]
   64 |     int nodeb=0;
      |         ^~~~~
dreaming.cpp:65:13: warning: unused variable 'c' [-Wunused-variable]
   65 |     int a,b,c,e;
      |             ^
dreaming.cpp:65:15: warning: unused variable 'e' [-Wunused-variable]
   65 |     int a,b,c,e;
      |               ^
dreaming.cpp:67:8: warning: unused variable 'bestb' [-Wunused-variable]
   67 |     ll bestb=INF;
      |        ^~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:144:13: warning: unused variable 'nodeb' [-Wunused-variable]
  144 |         int nodeb=-1;
      |             ^~~~~
dreaming.cpp:145:12: warning: unused variable 'bestb' [-Wunused-variable]
  145 |         ll bestb=INF;
      |            ^~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23