PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Flame Storm
Tester: Harris Leung
Editorialist: Aman Dwivedi
DIFFICULTY:
EasyMedium
PREREQUISITES:
Graphs & Observation
PROBLEM:
You have a simple graph (unweighted, undirected graph containing no selfloops or multiple edges) G with N vertices and M edges. There is an edge between two sellers if and only if they are neighbors. When you buy a mango from a seller numbered XX, the following occurs:
 Seller X keeps his price the same.
 Every seller Y who is a neighbor of X increases their price by 1, that is, A_Y=A_Y+1 for every Y who is a neighbor of X.
 Every other seller Z who is not a neighbor of X decreases their price by 1; that is, A_Z=A_Z−1 for every Z who is not a neighbor of X.
You need to process Q queries and find the minimum amount of money you need to pay so that you can buy exactly one mango from every seller when the query is ?.
Other queries involve the addition and deletion of the edges from the given graph.
QUICK EXPLANATION:
Let’s say S is the sum of the initial prices given to us and E is the number of edges in the graph at the output query time. Then the answer for each query will be:
where X is the missing edges in the graph at the query time.
EXPLANATION:
You might be wondering which seller to go to first and then who will be next. You may be trying to find a sequence in which order you need to visit the seller. Because if this is not where you are stuck, then you are on the right track.
So why does the order of visiting the seller doesn’t matter?
Let’s consider two nodes of the graph say u and v. Now think of the two scenarios possible:
1) u and v have an edge between them.

In this case, what happens when we visit the seller u first the seller v is going to increase his/her price by 1. Or, if you visit seller v first, then the seller u is going to increase his/her price by 1.

Hence for every edge the overall price increases by 1 for you.
2) u and v don’t have an edge between them.

In this case, what happens when we visit the seller u first the seller v is going to decrease his/her price by 1. Or, if you visit seller v first, then the seller u is going to decrease his/her price by 1.

Hence for every edge the overall price decreases by 1 for you.
Hence we can make two observations from the above scenarios:
 It doesn’t matter which node you visit first or which node you visit last.
 For every edge, the price increases by 1 while for every missing edge the price decreases by 1.
Therefore we just need to track the number of edges in the graph when we process the output query. If we know the number of edges in the graph then we can easily calculate the missing edges and so our answer.
TIME COMPLEXITY:
O(N+M+Q)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
long long sum = 0;
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
sum += x;
}
long long edges = (long long)m, unused = ((long long)n * (n  1)) / 2LL  edges;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
char x;
cin >> x;
if (x == '+') {
edges++;
unused;
int u, v;
cin >> u >> v;
}
else if (x == '') {
edges;
unused++;
int u, v;
cin >> u >> v;
}
else if (x == '?') {
cout << sum + edges  unused << '\n';
}
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
int n,m;
ll a[300001];
ll s=0;
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='') {
assert(fi==1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g'0';
if(cnt==0) {
fi=g'0';
}
cnt++;
assert(fi!=0  cnt==1);
assert(fi!=0  is_neg==false);
assert(!(cnt>19  ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
map<pair<int,int>,int>mp;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
n=readIntSp(1,100000);
m=readIntLn(1,min(1LL*n*(n1)/2,100000LL));
for(int i=1; i<=n ;i++){
if(i!=n) a[i]=readIntSp(1,1000000000);
else a[i]=readIntLn(1,1000000000);
s+=a[i];
}
for(int i=1; i<=m ;i++){
int u,v;
u=readIntSp(1,n);
v=readIntLn(1,n);
if(u>v) swap(u,v);
assert((mp[{u,v}]==0));
mp[{u,v}]=1;
}
ll cm=m;
int q;q=readIntLn(1,100000);
for(int i=1; i<=q ;i++){
char t;int u,v;
t=getchar();
if(t=='?'){
char c=getchar();assert(c=='\n');
cout << s+2*cm1LL*n*(n1)/2 << '\n';
//cm=m;
}
else if(t=='+'){
char c=getchar();assert(c==' ');
u=readIntSp(1,n);
v=readIntLn(1,n);
if(u>v) swap(u,v);
cm++;
assert((mp[{u,v}]==0));
mp[{u,v}]=1;
}
else if(t==''){
char c=getchar();assert(c==' ');
u=readIntSp(1,n);
v=readIntLn(1,n);
if(u>v) swap(u,v);
cm;
assert((mp[{u,v}]==1));
mp[{u,v}]=0;
}
else assert(false);
}
readEOF();
}
Editorialist Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
int n,edges;
cin>>n>>edges;
int total = n*(n1);
total/=2;
int missing_edges = totaledges;
int sum = 0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
sum+=x;
}
for(int i=0;i<edges;i++)
{
int waste;
cin>>waste>>waste;
}
int q;
cin>>q;
while(q)
{
char ch;
cin>>ch;
if(ch == '+')
{
int waste;
cin>>waste>>waste;
edges++;
missing_edges;
}
else if(ch == '')
{
int waste;
cin>>waste>>waste;
edges;
missing_edges++;
}
else
cout<<sum+edgesmissing_edges<<"\n";
}
return 0;
}