提出 #67364814

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define cty cout<<"YES"<<endl
#define ctn cout<<"NO"<<endl
int d[200010];
vector<int> v[200010];
bool vis[200010];
int n;
int f[200010][2];
int ans = 0;
void dfs(int x){
	vis[x] = true;
    vector<int> tmp;
    for(int i : v[x]){
        if(d[i]>=4&&!vis[i]){
            dfs(i);
            tmp.push_back(f[i][1]);
        }
    }
    sort(tmp.rbegin(),tmp.rend());
    f[x][1] = 1;
    for(int i = 0;i < tmp.size()&&i < 3; i++) f[x][1]+=tmp[i];
    f[x][0] = f[x][1]+(tmp.size()>=4?tmp[3]:0);
	ans = max(ans,f[x][0]);
}
void LonelyLunar_solve(){
    cin>>n;
    for(int i = 1;i < n; i++){
		int a,b;
		cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        d[a]++,d[b]++;
    }
    for(int i = 1;i <= n; i++){
		if(d[i]>=4&&!vis[i]) dfs(i);
    }
    if(ans == 0) cout<<"-1"<<endl;
    else cout<<ans*3+2<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin>>t;
    while(t--){
        LonelyLunar_solve();
    }
}

提出情報

提出日時
問題 F - Alkane
ユーザ ReguLarFighting
言語 C++ 20 (gcc 12.2)
得点 500
コード長 1118 Byte
結果 AC
実行時間 65 ms
メモリ 24056 KiB

コンパイルエラー

Main.cpp: In function ‘void dfs(int)’:
Main.cpp:24:21: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   24 |     for(int i = 0;i < tmp.size()&&i < 3; i++) f[x][1]+=tmp[i];
      |                   ~~^~~~~~~~~~~~

ジャッジ結果

セット名 Sample All After Contest
得点 / 配点 0 / 0 500 / 500 0 / 0
結果
AC × 3
AC × 59
AC × 1
セット名 テストケース
Sample sample00.txt, sample01.txt, sample02.txt
All sample00.txt, sample01.txt, sample02.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt, testcase31.txt, testcase32.txt, testcase33.txt, testcase34.txt, testcase35.txt, testcase36.txt, testcase37.txt, testcase38.txt, testcase39.txt, testcase40.txt, testcase41.txt, testcase42.txt, testcase43.txt, testcase44.txt, testcase45.txt, testcase46.txt, testcase47.txt, testcase48.txt, testcase49.txt, testcase50.txt, testcase51.txt, hand00.txt, hand01.txt, hand02.txt, hand03.txt
After Contest after_contest00.txt
ケース名 結果 実行時間 メモリ
after_contest00.txt AC 26 ms 15776 KiB
hand00.txt AC 2 ms 3516 KiB
hand01.txt AC 2 ms 3576 KiB
hand02.txt AC 2 ms 3644 KiB
hand03.txt AC 2 ms 3644 KiB
sample00.txt AC 2 ms 3440 KiB
sample01.txt AC 2 ms 3512 KiB
sample02.txt AC 2 ms 3436 KiB
testcase00.txt AC 2 ms 3432 KiB
testcase01.txt AC 2 ms 3456 KiB
testcase02.txt AC 2 ms 3440 KiB
testcase03.txt AC 2 ms 3516 KiB
testcase04.txt AC 55 ms 15904 KiB
testcase05.txt AC 57 ms 16920 KiB
testcase06.txt AC 19 ms 8560 KiB
testcase07.txt AC 57 ms 16924 KiB
testcase08.txt AC 19 ms 8488 KiB
testcase09.txt AC 56 ms 16988 KiB
testcase10.txt AC 25 ms 12648 KiB
testcase11.txt AC 65 ms 24056 KiB
testcase12.txt AC 28 ms 10712 KiB
testcase13.txt AC 56 ms 16840 KiB
testcase14.txt AC 44 ms 14432 KiB
testcase15.txt AC 57 ms 16964 KiB
testcase16.txt AC 51 ms 16088 KiB
testcase17.txt AC 55 ms 16924 KiB
testcase18.txt AC 58 ms 16956 KiB
testcase19.txt AC 60 ms 16844 KiB
testcase20.txt AC 31 ms 11240 KiB
testcase21.txt AC 56 ms 16928 KiB
testcase22.txt AC 30 ms 11464 KiB
testcase23.txt AC 49 ms 15236 KiB
testcase24.txt AC 49 ms 14684 KiB
testcase25.txt AC 51 ms 15224 KiB
testcase26.txt AC 24 ms 9836 KiB
testcase27.txt AC 48 ms 15216 KiB
testcase28.txt AC 44 ms 14456 KiB
testcase29.txt AC 48 ms 15308 KiB
testcase30.txt AC 45 ms 13936 KiB
testcase31.txt AC 48 ms 15236 KiB
testcase32.txt AC 26 ms 11040 KiB
testcase33.txt AC 51 ms 17200 KiB
testcase34.txt AC 11 ms 6716 KiB
testcase35.txt AC 53 ms 17144 KiB
testcase36.txt AC 24 ms 10368 KiB
testcase37.txt AC 51 ms 17120 KiB
testcase38.txt AC 29 ms 11980 KiB
testcase39.txt AC 54 ms 17068 KiB
testcase40.txt AC 42 ms 14884 KiB
testcase41.txt AC 51 ms 17188 KiB
testcase42.txt AC 21 ms 9620 KiB
testcase43.txt AC 51 ms 17204 KiB
testcase44.txt AC 45 ms 15004 KiB
testcase45.txt AC 53 ms 17060 KiB
testcase46.txt AC 20 ms 9344 KiB
testcase47.txt AC 52 ms 17200 KiB
testcase48.txt AC 15 ms 7680 KiB
testcase49.txt AC 53 ms 17260 KiB
testcase50.txt AC 49 ms 16704 KiB
testcase51.txt AC 51 ms 17276 KiB