oj.uz

답안 #592890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
592890 2022-07-09T18:32:07 Z chirathnirodha 꿈 (IOI13_dreaming) C++17
0 / 100
 52 ms 20940 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first 
#define S second 
#define P push
#define I insert
typedef long long ll;
const ll INF=1000000000000000;
const int maxn=100000;
int n,m,l;
vector<pair<int,ll> > v[maxn];
vector<int> rts;
int parent[maxn];
ll maxsublen[maxn];
ll maxlen[maxn];
int gr[maxn];
ll dfs(int x,int z){
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i].F;
        if(parent[x]==y)continue;
        parent[y]=x;
        gr[y]=z;
        maxsublen[x]=max(maxsublen[x],dfs(y,z)+v[x][i].S);
    }
    return maxsublen[x];
}
void dfs1(int x,ll maxpar){
    vector<pair<ll,int> > subs;
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i].F;
        if(parent[x]==y)continue;
        subs.PB(MP(maxsublen[y]+v[x][i].S,y));
    }
    sort(subs.rbegin(),subs.rend());
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i].F;
        if(parent[x]==y)continue;
        ll nmaxpar;
        if(subs[0].S==y && subs.size()>1)nmaxpar=max(maxpar,subs[1].F);
        else nmaxpar=max(maxpar,subs[0].F);
        nmaxpar+=v[x][i].S;
        maxlen[y]=max(maxsublen[y],nmaxpar);
        dfs1(y,nmaxpar);
    }
    return;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N;m=M;l=L;
    for(int i=0;i<m;i++){
        v[A[i]].PB(MP(B[i],(ll)T[i]));
        v[B[i]].PB(MP(A[i],(ll)T[i]));
    }
    memset(parent,-1,sizeof(parent));
    memset(maxsublen,0,sizeof(maxsublen));
    for(int i=0;i<n;i++){
        if(parent[i]!=-1)continue;
        parent[i]=i;
        rts.PB(i);
        gr[i]=rts.size()-1;
        dfs(i,rts.size()-1);
        maxlen[i]=maxsublen[i];
        dfs1(i,0);
    }
    ll grmin[rts.size()];
    for(int i=0;i<rts.size();i++)grmin[i]=INF;
    for(int i=0;i<n;i++){
        grmin[gr[i]]=min(grmin[gr[i]],maxlen[i]);
    }
    sort(grmin,grmin+rts.size());
    ll ans=INF;
    if(rts.size()==1)ans=grmin[0];
    else if(rts.size()==2)ans=grmin[0]+grmin[1]+l;
    else {
        ans=min(grmin[0]+grmin[1]+l,grmin[1]+grmin[2]+2*l);
    }
    return ans;
}

Compilation message

dreaming.cpp: In function 'll dfs(int, int)':
dreaming.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs1(int, ll)':
dreaming.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
dreaming.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<rts.size();i++)grmin[i]=INF;
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 20940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 20940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 8524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 20940 KB Output isn't correct
2 Halted 0 ms 0 KB -