Eventual … Journey

The first line contains two integers $n, m~(1 \leq n \leq 10^5, 0 \leq m \leq 10^5)$ , the numbers of stations and public railways.

The next line contains n integers $A_i~(A_i \in \{0,1\}, i = 1, 2, \dots, n)$ , separated by spaces, describing the owner of each station.

if the station i belongs to JR west, and vice versa.

The following m lines describe all the public railways, each of which contains two integers $u, v~(1 \leq u, v \leq n, u \neq v)$ , representing a bidirectional railway connecting u and v. It is guaranteed that no two public railways connect the same pair of stations, and Rikka is able to travel between every pair of stations. Notice that the private railways are not given directly in the input, and Rikka may have to use her passes rather than traveling only through the public railways.

C++14(g++5.4) 解法, 执行用时: 122ms, 内存消耗: 7160K, 提交时间: 2019-01-12 12:42:07

#include<iostream>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1e5+5;
int n,m;
bool ww[maxn];
int a[maxn],b[maxn];
vector<int>G[maxn];
int q1[2],q2[2];
int u,v;
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u); 
	}
	memset(ww,false,sizeof(ww));
	for (int i=1;i<=n;i++)
		for (int j=0;j<G[i].size();j++)
			if(a[G[i][j]]!=a[i]){
				ww[i]=true;
				b[i]++;
			} 
	
	for (int i=1;i<=n;i++){
		if (ww[i])
			q1[a[i]]++;
		else
			q2[a[i]]++;
	}
	for (int i=1;i<=n;i++){
		int ans=0;
		if (ww[i]){
			ans+=q1[a[i]]+q2[a[i]]+b[i]-1;
			ans+=(q1[a[i]^1]-b[i])*2+q2[a[i]^1]*2;
		}else{
			ans+=q1[a[i]]+q2[a[i]]-1;
			ans+=(q1[a[i]^1])*2+q2[a[i]^1]*3;
		}
		printf("%d ",ans); 
	}
}

C++(g++ 7.5.0) 解法, 执行用时: 47ms, 内存消耗: 2060K, 提交时间: 2022-11-02 23:18:23

#include <bits/stdc++.h>

const int MAX_N = 1e5 + 10 ;

int n , m , cnt[2] , mx[2] , ner[MAX_N] , a[MAX_N] ;

int main() {
	scanf("%d %d" , &n , &m) ;
	for (int i = 1 ; i <= n ; ++i)
		scanf("%d" , &a[i]) , ++cnt[a[i]] ;
	for (; m-- ;) {
		int x , y ; scanf("%d %d" , &x , &y) ;
		if (a[x] != a[y]) {
			++ner[x] ; ++ner[y] ;
		}
	}

	///

	for (int i = 1 ; i <= n ; ++i) if (ner[i]) ++mx[a[i]] ;
	for (int i = 1 ; i <= n ; ++i) {
		int op = a[i] , ans = cnt[op] + cnt[op ^ 1] * 3 - 1 - mx[op ^ 1] ;
		if (ner[i]) ans = cnt[op] + cnt[op ^ 1] * 2 - 1 - ner[i] ;
		printf("%d " , ans) ;
	}

	return 0 ;
}

C++(clang++11) 解法, 执行用时: 76ms, 内存消耗: 1872K, 提交时间: 2021-04-10 13:51:51

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int c1[2],c2[2],a[100010],d[100010];
int main()
{
	int n,m,i;cin>>n>>m;
	for (i=1;i<=n;i++)
	{
		cin>>a[i];c1[a[i]]++;
	}
	for (i=1;i<=m;i++)
	{
		int u,v;cin>>u>>v;
		if (a[u]!=a[v]) d[u]++,d[v]++;
	}
	for (i=1;i<=n;i++) if (!d[i]) c2[a[i]]++;
	for (i=1;i<=n;i++)
	{
		int w1,w2,w3=0;
		w1=c1[a[i]]-1+d[i];
		if (!d[i]) w3=c2[1-a[i]];
		w2=n-1-w1-w3;
		cout<<w1+2*w2+3*w3<<' ';
	}
}

详情