oj.uz

Submission #1029114

# Submission time Handle Problem Language Result Execution time Memory
1029114 2024-07-20T12:35:53 Z YassineBenYounes Longest Trip (IOI23_longesttrip) C++17
5 / 100
 1000 ms 1360 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 = 305;
const int LOG = 22;
const int inf = 1e9;
const ll mod = 998244353;
const int sq = 320;

vi graph[mx];

bool vis[mx];

vi ans;

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 = rng() % 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{
        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();
            int node = 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 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:104:17: warning: unused variable 'node' [-Wunused-variable]
  104 |             int node = rng() % N;
      |                 ^~~~
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 0 ms 344 KB Output is correct
2 Correct 262 ms 816 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 0 ms 344 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Correct 167 ms 344 KB Output is correct
4 Correct 473 ms 592 KB Output is correct
5 Execution timed out 1033 ms 1124 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 166 ms 344 KB Output is correct
4 Correct 456 ms 488 KB Output is correct
5 Execution timed out 1012 ms 888 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 17 ms 344 KB Output is correct
3 Partially correct 138 ms 344 KB Output is partially correct
4 Partially correct 486 ms 472 KB Output is partially correct
5 Partially correct 972 ms 964 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Partially correct 155 ms 344 KB Output is partially correct
9 Partially correct 354 ms 344 KB Output is partially correct
10 Partially correct 977 ms 884 KB Output is partially correct
11 Partially correct 938 ms 864 KB Output is partially correct
12 Partially correct 907 ms 1360 KB Output is partially correct
13 Partially correct 888 ms 724 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 35 ms 344 KB Output is correct
17 Partially correct 93 ms 344 KB Output is partially correct
18 Partially correct 143 ms 600 KB Output is partially correct
19 Partially correct 280 ms 344 KB Output is partially correct
20 Partially correct 307 ms 1112 KB Output is partially correct
21 Correct 6 ms 344 KB Output is correct
22 Correct 8 ms 344 KB Output is correct
23 Correct 21 ms 344 KB Output is correct
24 Correct 18 ms 344 KB Output is correct
25 Correct 13 ms 344 KB Output is correct
26 Partially correct 164 ms 344 KB Output is partially correct
27 Partially correct 172 ms 344 KB Output is partially correct
28 Partially correct 179 ms 344 KB Output is partially correct
29 Partially correct 297 ms 684 KB Output is partially correct
30 Partially correct 288 ms 600 KB Output is partially correct
31 Partially correct 297 ms 600 KB Output is partially correct
32 Correct 7 ms 344 KB Output is correct
33 Correct 8 ms 344 KB Output is correct
34 Correct 23 ms 344 KB Output is correct
35 Correct 28 ms 344 KB Output is correct
36 Correct 22 ms 344 KB Output is correct
37 Partially correct 183 ms 460 KB Output is partially correct
38 Partially correct 195 ms 344 KB Output is partially correct
39 Incorrect 55 ms 600 KB Incorrect
40 Halted 0 ms 0 KB -