oj.uz

답안 #1029123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029123 2024-07-20T12:50:13 Z YassineBenYounes 가장 긴 여행 (IOI23_longesttrip) C++17
15 / 100
 1000 ms 1316 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 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 < 20;j++){
                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 Execution timed out 1193 ms 736 KB Time limit exceeded
3 Halted 0 ms 0 KB -

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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Correct 134 ms 344 KB Output is correct
4 Correct 426 ms 616 KB Output is correct
5 Correct 956 ms 1264 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Correct 135 ms 472 KB Output is correct
9 Correct 334 ms 600 KB Output is correct
10 Correct 851 ms 1084 KB Output is correct
11 Correct 850 ms 996 KB Output is correct
12 Correct 901 ms 760 KB Output is correct
13 Correct 847 ms 1316 KB Output is correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 47 ms 344 KB Output is correct
3 Correct 411 ms 344 KB Output is correct
4 Execution timed out 1356 ms 728 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 344 KB Output is correct
2 Correct 45 ms 344 KB Output is correct
3 Partially correct 402 ms 464 KB Output is partially correct
4 Execution timed out 1452 ms 732 KB Time limit exceeded
5 Halted 0 ms 0 KB -