oj.uz

Submission #329964

# Submission time Handle Problem Language Result Execution time Memory
329964 2020-11-23T09:46:14 Z AmineWeslati Stations (IOI20_stations) C++14
100 / 100
 1061 ms 1404 KB 
//Never stop trying
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/
#include "bits/stdc++.h"
#ifndef LOCAL
#include "stations.h"
#endif
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 1500 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}

#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

vi labels;
vi adj[MX];
int cnt;

void dfs(int u, int p, int st){
	if(st==0){
		labels[u]=++cnt;
		for(auto v: adj[u]) if(v!=p) dfs(v,u,(st+1)%2);
	}
	else{
		for(auto v: adj[u]) if(v!=p) dfs(v,u,(st+1)%2);
		labels[u]=++cnt;
	}
}

vi label(int n, int k, vi u, vi v){
	labels.resize(n);
	FOR(i,0,n) adj[i].clear();
	FOR(i,0,n-1) adj[u[i]].pb(v[i]),adj[v[i]].pb(u[i]);
	cnt=-1;
	dfs(0,0,0);
	return labels;
}

int find_next_station(int s, int t, vi c) {
	if(sz(c)==1) return c[0];
	bool allSmaller=true;
	for(auto x: c) if(x>=s) allSmaller=false;

	if(allSmaller){
		FOR(i,1-(s==0),sz(c)-1){
			if(t>=c[i] && t<c[i+1]) return c[i];
		}
		if(t>=c.back() && t<s) return c.back();
		return c[0];

	}
	else{
		bool allBigger=true;
		for(auto x: c) if(x<=s) allBigger=false;
		//assert(allBigger);

		FOR(i,0,sz(c)-1-(s!=0)){
			if(t>c[i] && t<=c[i+1]) return c[i+1];
		}
		if(t>s && t<=c[0]) return c[0];
		assert(s!=0);
		return c.back();
	}
	return -1;
}

#ifdef LOCAL
int main() {
    boost; IO();

    int N; cin>>N;
    vi u(N-1),v(N-1);
    FOR(i,0,N) {cin>>u[i]>>v[i]; u[i]--; v[i]--;}
    vi res=label(N,1000,u,v);
    for(auto x: res) cout << x << ' '; cout << endl;

    FOR(i,0,N) FOR(j,0,N) if(i!=j){
    	vi vec; for(auto v: adj[i]) vec.pb(res[v]);
    	sort(all(vec));
    	if(find_next_station(res[i],res[j],vec)==-1){
    		dbgs(labels[i],labels[j]);
    	}
    }

    return 0;
}
#endif

/* Careful!!!
    .Array bounds
    .Infinite loops
    .Uninitialized variables / empty containers
    .Multisets are shit

   Some insights:
    .Binary search
    .Graph representation
    .Write brute force code
    .Change your approach
*/

Compilation message

stations.cpp: In function 'int find_next_station(int, int, vi)':
stations.cpp:106:8: warning: variable 'allBigger' set but not used [-Wunused-but-set-variable]
  106 |   bool allBigger=true;
      |        ^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 1076 KB Output is correct
2 Correct 522 ms 1076 KB Output is correct
3 Correct 1061 ms 936 KB Output is correct
4 Correct 696 ms 936 KB Output is correct
5 Correct 724 ms 936 KB Output is correct
6 Correct 466 ms 1080 KB Output is correct
7 Correct 454 ms 1228 KB Output is correct
8 Correct 3 ms 736 KB Output is correct
9 Correct 4 ms 776 KB Output is correct
10 Correct 2 ms 864 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 1112 KB Output is correct
2 Correct 539 ms 1008 KB Output is correct
3 Correct 898 ms 736 KB Output is correct
4 Correct 774 ms 936 KB Output is correct
5 Correct 617 ms 936 KB Output is correct
6 Correct 562 ms 736 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 864 KB Output is correct
2 Correct 514 ms 1068 KB Output is correct
3 Correct 978 ms 936 KB Output is correct
4 Correct 680 ms 936 KB Output is correct
5 Correct 600 ms 864 KB Output is correct
6 Correct 454 ms 992 KB Output is correct
7 Correct 490 ms 1108 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 5 ms 944 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 603 ms 736 KB Output is correct
12 Correct 473 ms 1100 KB Output is correct
13 Correct 501 ms 1204 KB Output is correct
14 Correct 512 ms 736 KB Output is correct
15 Correct 66 ms 736 KB Output is correct
16 Correct 80 ms 736 KB Output is correct
17 Correct 133 ms 736 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 864 KB Output is correct
2 Correct 700 ms 936 KB Output is correct
3 Correct 637 ms 936 KB Output is correct
4 Correct 3 ms 976 KB Output is correct
5 Correct 3 ms 864 KB Output is correct
6 Correct 2 ms 864 KB Output is correct
7 Correct 683 ms 1108 KB Output is correct
8 Correct 954 ms 936 KB Output is correct
9 Correct 734 ms 936 KB Output is correct
10 Correct 659 ms 736 KB Output is correct
11 Correct 7 ms 864 KB Output is correct
12 Correct 7 ms 864 KB Output is correct
13 Correct 7 ms 936 KB Output is correct
14 Correct 5 ms 944 KB Output is correct
15 Correct 2 ms 864 KB Output is correct
16 Correct 551 ms 736 KB Output is correct
17 Correct 522 ms 1040 KB Output is correct
18 Correct 529 ms 936 KB Output is correct
19 Correct 602 ms 936 KB Output is correct
20 Correct 622 ms 736 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 1252 KB Output is correct
2 Correct 575 ms 1120 KB Output is correct
3 Correct 982 ms 864 KB Output is correct
4 Correct 708 ms 1116 KB Output is correct
5 Correct 590 ms 864 KB Output is correct
6 Correct 481 ms 1076 KB Output is correct
7 Correct 473 ms 1112 KB Output is correct
8 Correct 3 ms 736 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 2 ms 944 KB Output is correct
11 Correct 464 ms 736 KB Output is correct
12 Correct 627 ms 876 KB Output is correct
13 Correct 942 ms 864 KB Output is correct
14 Correct 654 ms 936 KB Output is correct
15 Correct 628 ms 992 KB Output is correct
16 Correct 486 ms 736 KB Output is correct
17 Correct 699 ms 736 KB Output is correct
18 Correct 565 ms 1120 KB Output is correct
19 Correct 564 ms 1204 KB Output is correct
20 Correct 488 ms 1012 KB Output is correct
21 Correct 55 ms 1120 KB Output is correct
22 Correct 89 ms 864 KB Output is correct
23 Correct 120 ms 996 KB Output is correct
24 Correct 5 ms 776 KB Output is correct
25 Correct 6 ms 776 KB Output is correct
26 Correct 4 ms 776 KB Output is correct
27 Correct 3 ms 904 KB Output is correct
28 Correct 2 ms 936 KB Output is correct
29 Correct 548 ms 1156 KB Output is correct
30 Correct 524 ms 936 KB Output is correct
31 Correct 616 ms 864 KB Output is correct
32 Correct 552 ms 736 KB Output is correct
33 Correct 560 ms 736 KB Output is correct
34 Correct 336 ms 992 KB Output is correct
35 Correct 483 ms 1064 KB Output is correct
36 Correct 446 ms 992 KB Output is correct
37 Correct 557 ms 1116 KB Output is correct
38 Correct 480 ms 1120 KB Output is correct
39 Correct 511 ms 864 KB Output is correct
40 Correct 485 ms 1248 KB Output is correct
41 Correct 525 ms 1404 KB Output is correct
42 Correct 61 ms 892 KB Output is correct
43 Correct 119 ms 864 KB Output is correct
44 Correct 166 ms 1104 KB Output is correct
45 Correct 156 ms 1108 KB Output is correct
46 Correct 352 ms 1024 KB Output is correct
47 Correct 335 ms 1236 KB Output is correct
48 Correct 57 ms 864 KB Output is correct
49 Correct 76 ms 992 KB Output is correct