CCF-CSP 201912-4区块链

最新推荐文章于 2023-04-19 17:59:42 发布

Adolphrocs

最新推荐文章于 2023-04-19 17:59:42 发布

阅读量1k

点赞数

分类专栏： CCF-CSP认证

本文链接：https://blog.csdn.net/Adolphrocs/article/details/104250816

版权

CCF-CSP认证专栏收录该内容

7 篇文章

订阅专栏

CCF-CSP 201912-4区块链

看了大佬博客（https://blog.csdn.net/richenyunqi/article/details/104155384）以后写的，本来想着看完按自己思路写，但是最后写出来差不多，但是我80分，运行超时。

#include <bits/stdc++.h>
using namespace std;

map<int, unordered_map<int, array<vector<int>, 2>>> operation;//operation[a][b][0/1]表示a时刻需要b节点需要接收的链和块
vector<vector<int>> ans(505,{0});
vector<int>graph[505];
int n,m;
int t, k;

bool Judge(vector<int> v1, vector<int> v2){
    if (v1.size() != v2.size()) return v1.size() > v2.size();
    if (v1.size() == v2.size()) return *v1.rbegin() < *v2.rbegin();
    return 0;
}

void diffuse(int u, int ti){
    for (auto v : graph[u]){
        if (Judge(ans[u], operation[ti][v][0]))
            operation[ti][v][0] = ans[u];
    }
}
void query(int a, int b){
    for (auto times: operation){
        int time = times.first;
        //cout << time << "\n";
        if (time > b) break;
        for (auto ope : times.second){
            int vertex = ope.first;
            auto link = ope.second[0];
            auto block = ope.second[1];
            bool flag1 = Judge(link, ans[vertex]);
            bool flag2 = block.size();
            if (flag1) ans[vertex] = link;
            if (flag2) {
                for (auto _ : block) ans[vertex].push_back(_);
            }
            if (flag1 || flag2){
                diffuse(vertex, time + t);
            }
        }
    }
    operation.erase(operation.begin(), operation.upper_bound(b));
    cout << ans[a].size();
    for (auto _ : ans[a]){
        cout << " " << _ ;
    }
    cout << "\n";
}

int main() {
    //freopen("out4.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    cin >> t >> k;
    while (k--){
        int a, b, c;
        cin >> a >> b;
        if (cin.get()=='\n' || cin.eof()){
            //cout << "$  " << a <<" " <<  b<<"\n";
            query(a, b);
        }else{
            cin >> c;
            operation[b][a][1].push_back(c);
            //cout << "$  " << a <<" "<< b << " " << c << "\n";
        }
    }
    return 0;
}