CSP202203-4 通信系统管理

一直是25分,太难受了。只过了一个y=m的点还有一个p=1的点。写了八个小时了,还是没写出来,要哭了。


```c++
#include <cstdio>
#include <map>
#include <queue>
#include <vector>
#define Pii pair<int,int>
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

using namespace std;
const int N=100005;
const int M=100005;

int n,m,k,u,v,x,y,l,p,q;
int alone,both;

map<pair<int,int>,int>myMap;
vector<pair<pair<int,int>,int> >vec[M];
vector<pair<pair<int,int>,int> >::iterator j;
struct cmp{
    bool operator() (Pii a,Pii b)
    {
        if(a.first==b.first) return a.second>b.second;
        return a.first<b.first;
    }
};

struct Heap{
    priority_queue<Pii,vector<Pii>,cmp >q1,q2;
    void Push(int x,int y)
    {
        if(x!=0) q1.push(mp(x,y));
    }
    Pii Top()
    {
        while(!q2.empty()&&q1.top()==q2.top())
        {
            q1.pop();
            q2.pop();
        }
        return q1.top();
    }
    void Del(int x,int y)
    {
        if(x!=0) q2.push(mp(x,y));
    }
    bool isEmpty()
    {
        while(!q2.empty()&&q1.top()==q2.top())
        {
            q1.pop();
            q2.pop();
        }
        return q1.empty();
    }
}que[N];

void work(int u,int v,int x)
{
    Pii cnt=mp(u,v);
    if(!que[u].isEmpty()&&!que[que[u].Top().second].isEmpty()&&que[que[u].Top().second].Top().second==u) --both;
    if(que[u].isEmpty()&&myMap[cnt]+x!=0) --alone;
    que[u].Del(myMap[cnt],v);
    myMap[cnt]+=x;
    que[u].Push(myMap[cnt],v);
    if(que[u].isEmpty()) ++alone;
    if(!que[u].isEmpty()&&!que[que[u].Top().second].isEmpty()&&que[que[u].Top().second].Top().second==u) ++both;
}

int main (void)
{
    freopen("1.txt","r",stdin);
    scanf("%d%d",&n,&m);
    alone=n;//没开始的时候,都没有通信额度,通信孤岛是n
    for(int i=1;i<=m;++i)
    {
        printf("第%d天:\n",i);
        scanf("%d",&k);
        while(k--)
        {
            scanf("%d%d%d%d",&u,&v,&x,&y);
            work(u,v,x);work(v,u,x);
            if(i+y-1<=m) vec[i+y-1].pb(mp(mp(u,v),x));
        }
        scanf("%d",&l);
        while(l--)
        {
            scanf("%d",&x);
            printf("%d\n",que[x].isEmpty()?0:que[x].Top().second);//过掉了y=m的点 
        }
        scanf("%d%d",&p,&q);
        if(p==1) printf("%d\n",alone);
        if(q==1) printf("%d\n",both);
        for(int aa=vec[i].size()-1;aa>=0;--aa)
        {
            u=vec[i][aa].first.first;
            v=vec[i][aa].first.second;
            x=vec[i][aa].second;
            work(u,v,-x);work(v,u,-x);
        }
    }
    return 0;
}

```