제출 #1121429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121429		peacebringer1667	Lost Array (NOI19_lostarray)	C++17	32 / 100	43 ms	13844 KiB

lostarray

#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){
	while (m--){
		int u,v,w;
		cin >> u >> v >> w;
		vec[u].push_back({v,w});
		vec[v].push_back({u,w});
		
		s[u].insert(w);
		s[v].insert(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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 21 / 21
• Subtask 5: 0 / 48