답안 #1029143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1029143	2024-07-20T12:56:10 Z	YassineBenYounes	가장 긴 여행 (IOI23_longesttrip)	C++17	40 / 100	911 ms	1476 KB

longesttrip

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-