oj.uz

Submission #1065276

# Submission time Handle Problem Language Result Execution time Memory
1065276 2024-08-19T05:44:09 Z LittleOrange Longest Trip (IOI23_longesttrip) C++17
40 / 100
 938 ms 848 KB 
#include "longesttrip.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;
struct dsu{
    ll c;
    vector<ll> p;
    dsu(ll N):c(N),p(N,-1){}
    ll g(ll i){
        return p[i]<0?i:p[i] = g(p[i]);
    }
    bool m(ll a, ll b){
        a = g(a),b=g(b);
        if(a==b) return false;
        c--;
        if(p[a]>p[b]) swap(a,b);
        p[a] += p[b];
        p[b] = a;
        return true;
    }
};

std::vector<int> longest_trip(int N, int D)
{
    mt19937_64 mt(random_device{}());
    ll n = N;
    if (D==3){
        vector<ll> r(n);
        iota(r.begin(),r.end(),0);
        return r;
    }
    vector<vector<ll>> a(n,vector<ll>(n,0));
    vector<ll> de(n,0);
    dsu d(n);
    for(ll i = 0;i<n;i++){
        for(ll j = i+1;j<n;j++){
            a[i][j] = a[j][i] = are_connected({i},{j});
            if(a[i][j]) d.m(i,j);
            de[i] += a[i][j];
            de[j] += a[i][j];
        }
    }
    if (d.c>1){
        ll g = d.g(0);
        for(ll i = 0;i<n;i++){
            ll j = d.g(i);
            if (d.p[j]<d.p[g]) g = j;
        }
        vector<ll> v;
        for(ll i = 0;i<n;i++){
            if (d.g(i)==g) v.push_back(i);
        }
        return v;
    }
    for(ll i = 0;i<n;i++){
        if(de[i] == 1){
            for(ll j = 0;j<n;j++) if(a[i][j]){
                for(ll k = 0;k<n;k++) if(k!=i&&a[j][k]){
                    vector<ll> v = {i,j,k};
                    for(ll x = 0;x<n;x++) if(x!=i&&x!=j&&x!=k) v.push_back(x);
                    return v;
                }
            }
        }
    }
    vector<ll> ret;
    vector<ll> ord(n);
    iota(ord.begin(),ord.end(),0);
    vector<ll> cur;
    cur.reserve(n);
    ll cnt = 5000;
    while(cnt--){
        shuffle(ord.begin(),ord.end(),mt);
        cur.push_back(ord[0]);
        for(ll i : ord){
            if (a[cur.back()][i]) cur.push_back(i);
        }
        if(cur.size()>ret.size()) ret = cur;
        cur.clear();
        if(ret.size()==n) break;
    }
    return ret;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:82:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   82 |         if(ret.size()==n) break;
      |            ~~~~~~~~~~^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 216 ms 688 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 139 ms 344 KB Output is correct
4 Correct 396 ms 344 KB Output is correct
5 Correct 865 ms 684 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 176 ms 344 KB Output is correct
9 Correct 286 ms 344 KB Output is correct
10 Correct 802 ms 684 KB Output is correct
11 Correct 862 ms 688 KB Output is correct
12 Correct 823 ms 684 KB Output is correct
13 Correct 837 ms 684 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 141 ms 344 KB Output is correct
4 Correct 401 ms 344 KB Output is correct
5 Correct 839 ms 684 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 30 ms 344 KB Output is correct
8 Correct 143 ms 344 KB Output is correct
9 Correct 324 ms 344 KB Output is correct
10 Correct 804 ms 688 KB Output is correct
11 Correct 785 ms 684 KB Output is correct
12 Correct 800 ms 684 KB Output is correct
13 Correct 805 ms 688 KB Output is correct
14 Correct 9 ms 344 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Correct 66 ms 344 KB Output is correct
17 Correct 158 ms 344 KB Output is correct
18 Correct 201 ms 432 KB Output is correct
19 Correct 380 ms 344 KB Output is correct
20 Correct 383 ms 344 KB Output is correct
21 Correct 880 ms 696 KB Output is correct
22 Correct 851 ms 696 KB Output is correct
23 Correct 889 ms 696 KB Output is correct
24 Correct 894 ms 688 KB Output is correct
25 Correct 9 ms 596 KB Output is correct
26 Correct 13 ms 344 KB Output is correct
27 Correct 24 ms 344 KB Output is correct
28 Correct 23 ms 340 KB Output is correct
29 Correct 20 ms 344 KB Output is correct
30 Correct 184 ms 344 KB Output is correct
31 Correct 198 ms 340 KB Output is correct
32 Correct 207 ms 344 KB Output is correct
33 Correct 276 ms 344 KB Output is correct
34 Correct 326 ms 344 KB Output is correct
35 Correct 343 ms 344 KB Output is correct
36 Correct 873 ms 692 KB Output is correct
37 Correct 807 ms 684 KB Output is correct
38 Correct 828 ms 688 KB Output is correct
39 Correct 766 ms 848 KB Output is correct
40 Correct 796 ms 684 KB Output is correct
41 Correct 832 ms 600 KB Output is correct
42 Correct 843 ms 600 KB Output is correct
43 Correct 851 ms 684 KB Output is correct
44 Correct 791 ms 684 KB Output is correct
45 Correct 11 ms 344 KB Output is correct
46 Correct 12 ms 344 KB Output is correct
47 Correct 22 ms 344 KB Output is correct
48 Correct 16 ms 344 KB Output is correct
49 Correct 29 ms 344 KB Output is correct
50 Correct 205 ms 344 KB Output is correct
51 Correct 254 ms 344 KB Output is correct
52 Correct 278 ms 344 KB Output is correct
53 Correct 290 ms 344 KB Output is correct
54 Correct 364 ms 344 KB Output is correct
55 Correct 347 ms 344 KB Output is correct
56 Correct 838 ms 688 KB Output is correct
57 Correct 842 ms 688 KB Output is correct
58 Correct 887 ms 688 KB Output is correct
59 Correct 898 ms 704 KB Output is correct
60 Correct 934 ms 684 KB Output is correct
61 Correct 918 ms 688 KB Output is correct
62 Correct 894 ms 688 KB Output is correct
63 Correct 938 ms 684 KB Output is correct
64 Correct 869 ms 688 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Partially correct 156 ms 344 KB Output is partially correct
4 Partially correct 389 ms 344 KB Output is partially correct
5 Partially correct 862 ms 848 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Partially correct 150 ms 344 KB Output is partially correct
9 Partially correct 335 ms 344 KB Output is partially correct
10 Partially correct 839 ms 848 KB Output is partially correct
11 Partially correct 864 ms 680 KB Output is partially correct
12 Partially correct 886 ms 684 KB Output is partially correct
13 Partially correct 810 ms 692 KB Output is partially correct
14 Correct 10 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Incorrect 9 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -