oj.uz

답안 #130544

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130544 2019-07-15T13:42:48 Z wilwxk 다리 (APIO19_bridges) C++14
16 / 100
 179 ms 8372 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN=5e4+5;
const int INF=1e9+9;
const int SQRN=304;
vector<pair<int, int> > g[MAXN];
int weight[MAXN];
int mn[MAXN], bini[MAXN], bfim[MAXN];
int n, m, q;
 
void precalc() {
	fill(bini, bini+m, MAXN);
	fill(mn, mn+m, INF);
	for(int i=0; i<m; i++) {
		bini[i/SQRN]=min(bini[i/SQRN], i);
		bfim[i/SQRN]=max(bfim[i/SQRN], i);
	}
}
 
void update(int ind, int val) {
	weight[ind]=val;
	int bind=ind/SQRN;
	if(val<=mn[bind]) {
		mn[bind]=val;
		return;
	}
	mn[bind]=val;
	for(int i=bini[bind]; i<=bfim[bind]; i++) mn[bind]=min(mn[bind], weight[i]);
}
 
int query(int cur, int val) {
	int resp=1;
	for(int i=cur; i<m; i++) {
		int bind=i/SQRN;
		if(weight[i]<val) break;
		if(mn[bind]>=val) resp+=(bfim[bind]-i+1), i=bfim[bind];
		else resp++;
	}
	// for(int i=0; i<=n/SQRN; i++) printf("%d >> %d %d >> %d\n", i, bini[i], bfim[i], mn[i]);
	// printf("qu %d %d >> %d\n", cur, val, resp);
	for(int i=cur-1; i>=0; i--) {
		int bind=i/SQRN;
		if(weight[i]<val) break;
		if(mn[bind]>=val) resp+=(i-bini[bind]+1), i=bini[bind];
		else resp++;
	}
	return resp;
}
 
int main() {
	scanf("%d %d", &n, &m);
	precalc();
	for(int i=0; i<m; i++) {
		int a, b, c; scanf("%d %d %d", &a, &b, &c); a--; b--;
		g[a].push_back({b, i}); g[b].push_back({a, i});
		weight[i]=c; 
	}
	for(int i=0; i<m; i++) update(i, weight[i]);
	scanf("%d", &q);
	while(q--) {
		int a, b, c; scanf("%d %d %d", &a, &b, &c);
		if(a==1) update(b-1, c);
		else printf("%d\n", query(b-1, c));
	}
 
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:55:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d %d %d", &a, &b, &c); a--; b--;
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:62:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d %d %d", &a, &b, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 4600 KB Output is correct
2 Correct 103 ms 4600 KB Output is correct
3 Correct 103 ms 4600 KB Output is correct
4 Correct 104 ms 4528 KB Output is correct
5 Correct 105 ms 4628 KB Output is correct
6 Correct 166 ms 4856 KB Output is correct
7 Correct 157 ms 4688 KB Output is correct
8 Correct 148 ms 4656 KB Output is correct
9 Correct 45 ms 2424 KB Output is correct
10 Correct 104 ms 4600 KB Output is correct
11 Correct 98 ms 4600 KB Output is correct
12 Correct 179 ms 4956 KB Output is correct
13 Correct 118 ms 4472 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 4088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 41 ms 8372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 4600 KB Output is correct
2 Correct 103 ms 4600 KB Output is correct
3 Correct 103 ms 4600 KB Output is correct
4 Correct 104 ms 4528 KB Output is correct
5 Correct 105 ms 4628 KB Output is correct
6 Correct 166 ms 4856 KB Output is correct
7 Correct 157 ms 4688 KB Output is correct
8 Correct 148 ms 4656 KB Output is correct
9 Correct 45 ms 2424 KB Output is correct
10 Correct 104 ms 4600 KB Output is correct
11 Correct 98 ms 4600 KB Output is correct
12 Correct 179 ms 4956 KB Output is correct
13 Correct 118 ms 4472 KB Output is correct
14 Incorrect 89 ms 4088 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -