oj.uz

Submission #1121430

# Submission time Handle Problem Language Result Execution time Memory
1121430 2024-11-29T02:41:42 Z peacebringer1667 Lost Array (NOI19_lostarray) C++17
100 / 100
 25 ms 9824 KB 
#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define db double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e5 + 5;

multiset <int> s[maxn];
int a[maxn];
vector <pir> vec[maxn];
bool mark[maxn];

void input(int n,int m){
	fill(a + 1,a + 1 + n,1);
	
	while (m--){
		int u,v,w;
		cin >> u >> v >> w;
		a[u] = max(a[u],w);
		a[v] = max(a[v],w);
	}
}

void solve(int n){
	fill(a + 1,a + n + 1,1);
	
	deque <pir> dq;
	for (int u = 1 ; u <= n ; u++)
	  if (s[u].size() && *s[u].begin() == *s[u].rbegin())
	  	dq.push_back({u,*s[u].begin()});
	
	while (dq.size()){
		int u = dq.front().fi,x = dq.front().se;
	    dq.pop_front();
	    
	    if (mark[u]) continue;
	    mark[u] = 1;
	    a[u] = x;
	    
	  	for (pir node : vec[u]){
	    	int v = node.fi,w = node.se;
	    	
	    	if (!mark[v]){
	    		s[v].erase(s[v].lower_bound(w));
	    		
	    		if (s[v].size() && *s[v].begin() == *s[v].rbegin())
	    		   dq.push_back({v,*s[v].begin()});
	    		else
	    		if (!s[v].size())
	    		   dq.push_back({v,w});
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,m;
	cin >> n >> m;
	input(n,m);
	
//	solve(n);
	for (int i = 1 ; i <= n ; i++) cout << a[i] << " ";

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7504 KB Output is correct
2 Correct 5 ms 7340 KB Output is correct
3 Correct 6 ms 7520 KB Output is correct
4 Correct 5 ms 7504 KB Output is correct
5 Correct 5 ms 7444 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7504 KB Output is correct
2 Correct 5 ms 7340 KB Output is correct
3 Correct 6 ms 7520 KB Output is correct
4 Correct 5 ms 7504 KB Output is correct
5 Correct 5 ms 7444 KB Output is correct
6 Correct 6 ms 7504 KB Output is correct
7 Correct 5 ms 7504 KB Output is correct
8 Correct 9 ms 8016 KB Output is correct
9 Correct 6 ms 7504 KB Output is correct
10 Correct 9 ms 7824 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7504 KB Output is correct
2 Correct 5 ms 7340 KB Output is correct
3 Correct 6 ms 7520 KB Output is correct
4 Correct 5 ms 7504 KB Output is correct
5 Correct 5 ms 7444 KB Output is correct
6 Correct 6 ms 7504 KB Output is correct
7 Correct 5 ms 7504 KB Output is correct
8 Correct 9 ms 8016 KB Output is correct
9 Correct 6 ms 7504 KB Output is correct
10 Correct 9 ms 7824 KB Output is correct
11 Correct 6 ms 7504 KB Output is correct
12 Correct 6 ms 7512 KB Output is correct
13 Correct 6 ms 7512 KB Output is correct
14 Correct 6 ms 7764 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7504 KB Output is correct
2 Correct 11 ms 7760 KB Output is correct
3 Correct 9 ms 7760 KB Output is correct
4 Correct 9 ms 7660 KB Output is correct
5 Correct 6 ms 7504 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7504 KB Output is correct
2 Correct 5 ms 7340 KB Output is correct
3 Correct 6 ms 7520 KB Output is correct
4 Correct 5 ms 7504 KB Output is correct
5 Correct 5 ms 7444 KB Output is correct
6 Correct 6 ms 7504 KB Output is correct
7 Correct 5 ms 7504 KB Output is correct
8 Correct 9 ms 8016 KB Output is correct
9 Correct 6 ms 7504 KB Output is correct
10 Correct 9 ms 7824 KB Output is correct
11 Correct 6 ms 7504 KB Output is correct
12 Correct 6 ms 7512 KB Output is correct
13 Correct 6 ms 7512 KB Output is correct
14 Correct 6 ms 7764 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct
16 Correct 7 ms 7504 KB Output is correct
17 Correct 11 ms 7760 KB Output is correct
18 Correct 9 ms 7760 KB Output is correct
19 Correct 9 ms 7660 KB Output is correct
20 Correct 6 ms 7504 KB Output is correct
21 Correct 15 ms 8536 KB Output is correct
22 Correct 16 ms 8556 KB Output is correct
23 Correct 19 ms 8984 KB Output is correct
24 Correct 18 ms 9056 KB Output is correct
25 Correct 25 ms 9824 KB Output is correct