oj.uz

Submission #1029143

# Submission time Handle Problem Language Result Execution time Memory
1029143 2024-07-20T12:56:10 Z YassineBenYounes Longest Trip (IOI23_longesttrip) C++17
40 / 100
 911 ms 1476 KB 
#include<bits/stdc++.h>
#include<chrono>
#include<random>
#include "longesttrip.h"
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1};
int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1};
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<pii, null_type, less<pii>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

////////////////////Only Clear Code//////////////////////////
 
void usaco_problem(){
    freopen("milkvisits.in", "r", stdin);
    freopen("milkvisits.out", "w", stdout);
}
 
void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}
const int mx = 260;
const int LOG = 22;
const int inf = 1e9;
const ll mod = 998244353;
const int sq = 320;

vi graph[mx];

bool vis[mx];

vi ans;
int key;
void dfs(int node){
    vis[node] = 1;
    ans.pb(node);
    vi v;
    for(int adj : graph[node]){
        if(vis[adj])continue;
        v.pb(adj);
    }
    int s = v.size();
    if(s == 0)return;
    int ind = key % s;
    dfs(v[ind]);
}
/*
bool are_connected(vi a, vi b){
    return 1;
}*/

vi longest_trip(int N, int D){
    if(D == 3){
        vi res;
        for(int i = 0; i < N;i++){
            res.pb(i);
        }
        return res;
    }
    else if(D == 2){
        for(int i = 0; i < N;i++){
            graph[i].clear();
        }
        for(int i = 0; i < N;i++){
            for(int j = i+1;j < N;j++){
                if(are_connected({i}, {j})){
                    graph[i].pb(j);
                    graph[j].pb(i);
                }
            }
        }
        vi res;
        for(int i = 0; i < N;i++){
            memset(vis, 0, sizeof vis);
            ans.clear();
            dfs(i);
            if(ans.size() > res.size())res = ans;
        }
        return res;
    }
    else{
        for(int i = 0; i < N;i++){
            graph[i].clear();
        }
        for(int i = 0; i < N;i++){
            for(int j = i+1;j < N;j++){
                if(are_connected({i}, {j})){
                    graph[i].pb(j);
                    graph[j].pb(i);
                }
            }
        }
        vi res;
        for(int i = 0; i < N;i++){
            //for(int j = 0;j < 2;j++){
                memset(vis, 0, sizeof vis);
                ans.clear();
                key = rng() % N;
                dfs(i);
                if(ans.size() > res.size())res = ans;
            //}
        }
        return res;
    }
}

/*
int32_t main(){
    init();
    speed;
    vi a = longest_trip(5, 2);
    cout << a.size() << endl;
    for(int x : a){
        cout << x << " ";
    }
    cout << endl;
}*/
/*
    NEVER GIVE UP!
    DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
    Your Guide when stuck:
    - Continue keyword only after reading the whole input
    - Don't use memset with testcases
    - Check for corner cases(n=1, n=0)
    - Check where you declare n(Be careful of declaring it globally and in main)
*/

Compilation message

longesttrip.cpp: In function 'void usaco_problem()':
longesttrip.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
longesttrip.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
longesttrip.cpp: In function 'void init()':
longesttrip.cpp:44:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
longesttrip.cpp:46:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 236 ms 1112 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 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 7 ms 344 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 153 ms 344 KB Output is correct
4 Correct 446 ms 600 KB Output is correct
5 Correct 805 ms 952 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 17 ms 344 KB Output is correct
8 Correct 128 ms 344 KB Output is correct
9 Correct 309 ms 848 KB Output is correct
10 Correct 768 ms 804 KB Output is correct
11 Correct 783 ms 1040 KB Output is correct
12 Correct 726 ms 888 KB Output is correct
13 Correct 679 ms 752 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 420 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 131 ms 344 KB Output is correct
4 Correct 386 ms 344 KB Output is correct
5 Correct 770 ms 880 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 155 ms 344 KB Output is correct
9 Correct 290 ms 344 KB Output is correct
10 Correct 771 ms 856 KB Output is correct
11 Correct 794 ms 1256 KB Output is correct
12 Correct 850 ms 972 KB Output is correct
13 Correct 769 ms 892 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 13 ms 344 KB Output is correct
16 Correct 31 ms 344 KB Output is correct
17 Correct 81 ms 344 KB Output is correct
18 Correct 125 ms 344 KB Output is correct
19 Correct 295 ms 516 KB Output is correct
20 Correct 290 ms 600 KB Output is correct
21 Correct 890 ms 1364 KB Output is correct
22 Correct 873 ms 1076 KB Output is correct
23 Correct 856 ms 1056 KB Output is correct
24 Correct 850 ms 1244 KB Output is correct
25 Correct 5 ms 344 KB Output is correct
26 Correct 10 ms 344 KB Output is correct
27 Correct 19 ms 344 KB Output is correct
28 Correct 22 ms 344 KB Output is correct
29 Correct 20 ms 344 KB Output is correct
30 Correct 183 ms 344 KB Output is correct
31 Correct 176 ms 472 KB Output is correct
32 Correct 179 ms 344 KB Output is correct
33 Correct 284 ms 864 KB Output is correct
34 Correct 295 ms 344 KB Output is correct
35 Correct 281 ms 344 KB Output is correct
36 Correct 818 ms 1032 KB Output is correct
37 Correct 848 ms 1104 KB Output is correct
38 Correct 811 ms 1100 KB Output is correct
39 Correct 776 ms 876 KB Output is correct
40 Correct 829 ms 1108 KB Output is correct
41 Correct 823 ms 752 KB Output is correct
42 Correct 871 ms 1152 KB Output is correct
43 Correct 756 ms 1096 KB Output is correct
44 Correct 812 ms 1040 KB Output is correct
45 Correct 8 ms 344 KB Output is correct
46 Correct 8 ms 344 KB Output is correct
47 Correct 25 ms 344 KB Output is correct
48 Correct 22 ms 344 KB Output is correct
49 Correct 19 ms 344 KB Output is correct
50 Correct 169 ms 344 KB Output is correct
51 Correct 194 ms 600 KB Output is correct
52 Correct 169 ms 344 KB Output is correct
53 Correct 276 ms 848 KB Output is correct
54 Correct 305 ms 520 KB Output is correct
55 Correct 303 ms 520 KB Output is correct
56 Correct 823 ms 1252 KB Output is correct
57 Correct 871 ms 888 KB Output is correct
58 Correct 831 ms 852 KB Output is correct
59 Correct 804 ms 908 KB Output is correct
60 Correct 741 ms 1300 KB Output is correct
61 Correct 772 ms 1228 KB Output is correct
62 Correct 769 ms 980 KB Output is correct
63 Correct 752 ms 1040 KB Output is correct
64 Correct 742 ms 804 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 25 ms 344 KB Output is correct
3 Partially correct 128 ms 344 KB Output is partially correct
4 Partially correct 423 ms 600 KB Output is partially correct
5 Partially correct 911 ms 1476 KB Output is partially correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 28 ms 344 KB Output is correct
8 Partially correct 132 ms 344 KB Output is partially correct
9 Partially correct 294 ms 484 KB Output is partially correct
10 Partially correct 826 ms 1132 KB Output is partially correct
11 Partially correct 850 ms 888 KB Output is partially correct
12 Partially correct 788 ms 856 KB Output is partially correct
13 Partially correct 781 ms 716 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 13 ms 344 KB Output is correct
16 Correct 31 ms 344 KB Output is correct
17 Partially correct 72 ms 344 KB Output is partially correct
18 Partially correct 121 ms 344 KB Output is partially correct
19 Partially correct 306 ms 480 KB Output is partially correct
20 Partially correct 290 ms 600 KB Output is partially correct
21 Correct 11 ms 344 KB Output is correct
22 Correct 7 ms 344 KB Output is correct
23 Correct 15 ms 344 KB Output is correct
24 Correct 25 ms 344 KB Output is correct
25 Correct 14 ms 344 KB Output is correct
26 Partially correct 183 ms 600 KB Output is partially correct
27 Partially correct 171 ms 592 KB Output is partially correct
28 Partially correct 192 ms 456 KB Output is partially correct
29 Partially correct 288 ms 592 KB Output is partially correct
30 Partially correct 278 ms 600 KB Output is partially correct
31 Partially correct 312 ms 344 KB Output is partially correct
32 Correct 5 ms 344 KB Output is correct
33 Correct 10 ms 344 KB Output is correct
34 Correct 19 ms 344 KB Output is correct
35 Correct 19 ms 344 KB Output is correct
36 Correct 33 ms 344 KB Output is correct
37 Partially correct 193 ms 344 KB Output is partially correct
38 Incorrect 10 ms 344 KB Incorrect
39 Halted 0 ms 0 KB -