oj.uz

Submission #60383

# Submission time Handle Problem Language Result Execution time Memory
60383 2018-07-24T04:28:55 Z ainta(#1738) Railway Trip (JOI17_railway_trip) C++11
0 / 100
 120 ms 11160 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#define N_ 101000
using namespace std;
int n, K, Q, w[N_], Num[N_];
vector<int>G[N_], E[N_], L[N_];
set<int>Set;
int BIT[N_][2];
void Add(int a, int ck, int b) {
	while (a <= n) {
		BIT[a][ck] += b;
		a += (a&-a);
	}
}
int Sum(int a, int ck) {
	int r = 0;
	while (a) {
		r += BIT[a][ck];
		a -= (a&-a);
	}
	return r;
}

void Add_Edge(int a, int b, int d) {
	E[a].push_back(b);
	L[a].push_back(d);
}

int cnt, v[N_];

void DFS(int a) {
	v[a] = cnt;
	for (auto &x : E[a]) {
		if (v[x]!=cnt)DFS(x);
	}
}

int main() {
	int i;
	scanf("%d%d%d", &n, &K, &Q);
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		G[w[i]].push_back(i);
	}
	for (i = K; i >= 1; i--) {
		if (G[i].empty())continue;
		for (auto &t : G[i]) {
			Add(t, 0, 1);
			Add(t, 1, 1);
		}
		if (Set.empty())continue;
		for (auto &t : G[i]) {
			auto it = Set.lower_bound(t);
			int d1 = 1e9, d2 = 1e9, l, r;
			if (it != Set.end()) {
				d2 = Sum(*it, 0) - Sum(t, 0) + 1;
				r = *it;
			}
			if (it != Set.begin()) {
				it--;
				d1 = Sum(t, 0) - Sum(*it, 0);
				l = *it;
			}
			int M = min(d1, d2);
			if (d1 == M) {
				Add_Edge(t, l, d1);
			}
			if (d2 == M) {
				Add_Edge(t, r, d2);
			}
		}
		for (auto &t : G[i]) {
			Set.insert(t);
			Num[t] = Sum(t, 1);
			Add(t, 0, -1);
		}
	}
	while (Q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		cnt++;
		DFS(a);
		cnt++;
		DFS(b);
	}
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &K, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i]);
   ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 9648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 11160 KB Output isn't correct
2 Halted 0 ms 0 KB -