oj.uz

답안 #1029116

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029116 2024-07-20T12:40:47 Z YassineBenYounes 가장 긴 여행 (IOI23_longesttrip) C++17
30 / 100
 1000 ms 1552 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;

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();
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 258 ms 1064 KB Output is correct

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Correct 179 ms 600 KB Output is correct
4 Correct 446 ms 464 KB Output is correct
5 Execution timed out 1006 ms 748 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Correct 158 ms 708 KB Output is correct
4 Correct 465 ms 492 KB Output is correct
5 Correct 994 ms 884 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 159 ms 468 KB Output is correct
9 Correct 322 ms 596 KB Output is correct
10 Correct 886 ms 848 KB Output is correct
11 Correct 894 ms 1248 KB Output is correct
12 Correct 888 ms 700 KB Output is correct
13 Correct 885 ms 1388 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 41 ms 344 KB Output is correct
17 Correct 86 ms 344 KB Output is correct
18 Correct 156 ms 1108 KB Output is correct
19 Correct 362 ms 344 KB Output is correct
20 Correct 360 ms 872 KB Output is correct
21 Correct 928 ms 1104 KB Output is correct
22 Correct 924 ms 1072 KB Output is correct
23 Correct 907 ms 1140 KB Output is correct
24 Correct 962 ms 1420 KB Output is correct
25 Correct 8 ms 344 KB Output is correct
26 Correct 6 ms 344 KB Output is correct
27 Correct 18 ms 344 KB Output is correct
28 Correct 15 ms 340 KB Output is correct
29 Correct 18 ms 344 KB Output is correct
30 Correct 187 ms 344 KB Output is correct
31 Correct 198 ms 716 KB Output is correct
32 Correct 182 ms 608 KB Output is correct
33 Correct 302 ms 864 KB Output is correct
34 Correct 325 ms 592 KB Output is correct
35 Correct 340 ms 692 KB Output is correct
36 Correct 856 ms 1312 KB Output is correct
37 Correct 943 ms 1104 KB Output is correct
38 Correct 897 ms 1100 KB Output is correct
39 Correct 811 ms 804 KB Output is correct
40 Correct 837 ms 1280 KB Output is correct
41 Correct 805 ms 1012 KB Output is correct
42 Correct 775 ms 824 KB Output is correct
43 Correct 790 ms 1136 KB Output is correct
44 Correct 788 ms 772 KB Output is correct
45 Correct 6 ms 344 KB Output is correct
46 Correct 8 ms 344 KB Output is correct
47 Correct 20 ms 344 KB Output is correct
48 Correct 21 ms 344 KB Output is correct
49 Correct 29 ms 344 KB Output is correct
50 Correct 188 ms 600 KB Output is correct
51 Correct 172 ms 456 KB Output is correct
52 Correct 187 ms 344 KB Output is correct
53 Correct 349 ms 476 KB Output is correct
54 Correct 389 ms 960 KB Output is correct
55 Correct 346 ms 592 KB Output is correct
56 Correct 882 ms 792 KB Output is correct
57 Correct 861 ms 952 KB Output is correct
58 Correct 895 ms 1036 KB Output is correct
59 Correct 824 ms 1552 KB Output is correct
60 Correct 873 ms 1236 KB Output is correct
61 Correct 831 ms 1032 KB Output is correct
62 Correct 730 ms 992 KB Output is correct
63 Correct 784 ms 800 KB Output is correct
64 Correct 810 ms 1044 KB Output is correct

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Partially correct 155 ms 344 KB Output is partially correct
4 Partially correct 502 ms 484 KB Output is partially correct
5 Partially correct 903 ms 752 KB Output is partially correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 29 ms 344 KB Output is correct
8 Partially correct 130 ms 600 KB Output is partially correct
9 Partially correct 311 ms 616 KB Output is partially correct
10 Partially correct 876 ms 856 KB Output is partially correct
11 Partially correct 894 ms 812 KB Output is partially correct
12 Partially correct 925 ms 1144 KB Output is partially correct
13 Execution timed out 1025 ms 1208 KB Time limit exceeded
14 Halted 0 ms 0 KB -