Submission #974782

#	Time	Username	Problem	Language	Result	Execution time	Memory
974782		Nika533	가장 긴 여행 (IOI23_longesttrip)	C++17	40 / 100	804 ms	848 KiB

longesttrip

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#include "longesttrip.h"
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
int n,m,T,k;

vector<int> longest_trip(int N, int D) {
	if (D==2) {
		vector<int> v;
		int fix[N];
		for (int i=0; i<N; i++) {
			fix[i]=0;
		}
		vector<int> v1,v2;
		for (int i=0; i<N; i++) {
			for (int j=i+1; j<N; j++) {
				vector<int> a,b; a.pb(i); b.pb(j);
				if (!are_connected(a,b)) {
					v1.pb(i); v2.pb(j);
					fix[i]=1; fix[j]=1;
				}
			}
		}
		for (auto x:v1) v.pb(x);
		for (int i=0; i<N; i++) if (!fix[i]) v.pb(i);
		for (auto x:v2) v.pb(x);
		return v;
	}
	
	vector<int> v;
	int e[N][N];
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			e[i][j]=0;
		}
	}
	vector<int> v1,v2;
	for (int i=0; i<N; i++) {
		for (int j=i+1; j<N; j++) {
			vector<int> a,b; a.pb(i); b.pb(j);
			if (are_connected(a,b)) {
				e[i][j]=1; e[j][i]=1;
			}
		}
	}
	int cur=0,mx=0; v.pb(cur);
	vector<int> c;
	for (int i=1; i<N; i++) {
		if (e[cur][i]) {
			v.pb(i);
			if (i-cur>1) {
				int l=mx+1,r=i-1;
				for (int j=l; j<=r; j++) c.pb(j);
			}
			cur=i; mx=i;
			int check=-1;
			for (auto j:c) {
				if (e[i][j]) check=j;
			}
			if (check!=-1) {
				v.pb(check);
				for (auto j:c) {
					if (j!=check) v.pb(j);
				}
				cur=v.back();
				c.clear();
			}
		}
	}
	for (int i=mx+1; i<N; i++) c.pb(i);
	if (c.size()>N/2) return c;
	return v;
}

Compilation message (stderr)

longesttrip.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:79:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |  if (c.size()>N/2) return c;
      |      ~~~~~~~~^~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 60