제출 #305747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305747		sofapuden	꿈 (IOI13_dreaming)	C++14	14 / 100	77 ms	15092 KiB

dreaming

    #include "dreaming.h"
    #include <bits/stdc++.h>
     
    using namespace std;
    vector<vector<pair<int,int>>> gri;
    vector<int> dis;
    vector<int> dep;
    vector<int> used;
    int jic = 0;
    int ans = 0;
    int y;
     
    int dfs2(int x, int p, int d){
    	int bes = 0;
    	int bes2 = 0;
    	for(int i = 0; i < gri[x].size(); ++i){
    		if(gri[x][i].first == p)continue;
    		int cur = dfs2(gri[x][i].first, x, d+gri[x][i].second);
    		if(bes < cur)swap(cur, bes);
    		if(bes2 < cur)swap(cur, bes2);
    	}
    	ans = max(ans, max(bes+bes2-2*d, d));
    	return max(d, bes);
    	
    }
    int dfs(int x, int p){
    	used[x] = 1;
    	int s = 0;
    	for(int i = 0; i < (int)gri[x].size(); ++i){
    		int z = 0;
    		if(gri[x][i].first != p)z = dfs(gri[x][i].first,x)+gri[x][i].second;
    		dep.push_back(z);
    		s+=z;
    	}
    	return s;
    }
    void find(int ind){
    	if(!gri[ind].size()){dis.push_back(0);return;}
    	dep.clear();
    	y = dfs(ind,ind);
    	int lll = dfs2(ind,ind,0);
    	jic = max(jic,lll);
    	int best = INT_MAX;
    	for(int i = 0; i < (int)dep.size(); ++i){
    		best = min(best, max(y-dep[i],dep[i]));
    	}
    	dis.push_back(best);	
    }
     
    int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
		if(N == 1)return 0;
		if(N == 2)return (M ? L : T[0]);
        used.resize(N,0);
        gri.resize(N);
        for(int i = 0; i < M; ++i){
    		gri[A[i]].push_back({B[i],T[i]});
    		gri[B[i]].push_back({A[i],T[i]});
    	}
    	for(int i = 0; i < N; ++i){
    		if(!used[i] && gri[i].size() == 1){
    			find(i);
    		}
    	}
    	sort(dis.rbegin(),dis.rend());
    	if(dis.size() >= 3){
			return max(jic,max(dis[0]+L+dis[1],dis[1]+dis[2]+2*L));
		}
		if(dis.size() == 2){
			return max(jic,dis[0]+L+dis[1]);
		}
		return jic;
    }

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

dreaming.cpp: In function 'int dfs2(int, int, int)':
dreaming.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |      for(int i = 0; i < gri[x].size(); ++i){
      |                     ~~^~~~~~~~~~~~~~~

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