欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CCF 201912-4 区块链

程序员文章站 2022-05-12 12:58:08
...

CCF 201912-4 区块链
CCF 201912-4 区块链
博主在2020年8月30日写的,运行什么的都没有错,但是到官网一直编译出错,没有用非标准的头文件,之后我去找了各位大佬的源码,不知道为啥也是编译出错,可能今天官网服务器有点问题吧,之后再试试看看是什么情况

题记
一开始输入的时候总是运行到一半自己退出来,最后发现是ios::sync_with_stdio(false);其实本来没什么问题,但是我用了getchar()读取换行符,这两个一块用就容易出问题,所以尽量还是用cin.get()度换行符比较稳妥。
因为代码内部注释很详细,所以别的就不再赘述了

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <sstream>
#include <unordered_map>

using namespace std;

//输入
int n,m,t,k;

vector<vector<int>> G;//邻接表形式的图
vector<vector<int>> links;//每个结点当前的主链
map<int,unordered_map<int,vector<int>>> rec;//时间-结点编号-收到的链 每个时刻对应的每个结点收到的链
map<int,unordered_map<int,vector<int>>> cre;//时间-结点编号-创造的块的编号(可能多个) 每个时刻对应的每个结点产生的新块

//输入
vector<int> input(){
    string line;
    getline(cin,line);
    stringstream stream(line);
    vector<int> vec;
    int temp;
    while(stream>>temp)
        vec.push_back(temp);
    return vec;
}

//更新time时刻结点index对收到的主链vec进行处理
void update(int time,int index,const vector<int>& vec){
    //取出来当前的主链(注意需要用引用,更新直接用cur)
    auto& cur=links[index];
    //如果收到的链比当前主链长或者一样长当时收到的链末尾块编号更小就更新
    if(vec.size()>cur.size()||vec.size()==cur.size()&&vec.back()<cur.back()){
        cur=vec;
        for(int neighbor:G[index]){
            //得到每个邻接点time+t时刻接受到的链(只保留最长的那一个)
            auto& temp=rec[time+t][neighbor];
            if(temp.size()<cur.size()||temp.size()==cur.size()&&cur.back()<temp.back()){
                temp=cur;
            }
        }
    }
}

//执行T时间及之前的操作
void execute_until(int T){
    auto rec_p=rec.begin();//rec_first指向当前保存的最早的接受链的信息
    auto cre_p=cre.begin();//cre_first指向当前保存的最早的产生新块的信息
    //只要这两个不都空就执行
    while(rec_p!=rec.end()||cre_p!=cre.end()){
        //如果所有新块更新完了(cre空了)或者rec不空而且接受的时间早于产生新块的时间
        if(cre_p==cre.end()||rec_p!=rec.end()&&rec_p->first<=cre_p->first){
            //当前执行的接受链的时间超过了查询时间,跳出循环
            if(rec_p->first>T)
                break;
            //对每一个在当前时间有接收到链的结点进行更新
            for(const auto& mp:rec_p->second){
                update(rec_p->first,mp.first,mp.second);
            }
            rec_p=rec.erase(rec_p);//使rec_first始终指向当前保存的最早的接受链的信息
        }
        else{
            if(cre_p->first>T)
                break;
            for(const auto& mp:cre_p->second){
                //得到产生新块的结点的主链
                auto temp=links[mp.first];
                temp.insert(temp.end(),mp.second.begin(),mp.second.end());
                update(cre_p->first,mp.first,temp);
            }
            cre_p=cre.erase(cre_p);
            rec_p=rec.begin();
        }
    }
}


int main()
{
    //加快cin,cout的速度
    ios::sync_with_stdio(false);
    cin>>n>>m;
    G.resize(n+1);
    links.resize(n+1,{0});
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin>>t>>k;
    //吃掉换行符
    cin.get();
    while(k--){
        vector<int> op;
        op=input();
        if(op.size()==3){
            cre[op[1]][op[0]].push_back(op[2]);
        }
        else{
            execute_until(op[1]);
            cout<<links[op[0]].size();
            for(int x:links[op[0]])
                cout<<" "<<x;
            cout<<endl;
        }
    }
    return 0;
}

样例输入1

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 27
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 10 10
2 11 9
1 11
2 11
3 11
4 11
5 11
1 12
2 12
3 12
4 12
5 12

样例输入2

15 13
1 2
2 3
3 4
4 5
1 6
6 7
7 8
8 9
1 10
10 11
11 12
12 13
14 15
6 28
1 1 1
1 2 2
1 6
2 7
13 7
9 7
5 7
3 14
8 14
5 14
11 14
9 25
5 25
13 25
9 28 3
5 29 4
13 29 5
1 53
2 59 6
2 59
1 1000
3 1000
8 1000
9 1000
10 1000
13 1000
14 1000
15 1000```