Ideone.com

fork download

copy

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<map>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
struct node{
    int n;
    int day;
    node(int a, int b){
        n = a;
        day = b;
    }
    bool operator  <(const node& p)const{
        return day > p.day;
    }
};
char str[50];
int prereq[28];
int total[28];
vector<int>check[27];
vector<int>res;
vector<int>edge[28];
priority_queue<node>q;
void dfs( int r,int rest){
 
    int minimum,x,j,i,y;
    vector<int>temp;
    total[r] = rest - total[r];
    for( i = 0; i < edge[r].size(); i++){
        x = edge[r][i];
        prereq[x]--;
        if( prereq[x] == 0){
            temp.push_back(x);
        }
        else{
            check[x].push_back(r);
        }
    }
    minimum = total[r];
    for( i = 0; i < temp.size(); i++){
        x = temp[i];
        for( j = 0; j < check[x].size(); j++){
            y = check[x][j];
            if(total[y] < minimum ){
                minimum = total[y];
            }
        }
        if( total[x] <= minimum ){
            dfs(x,minimum);
        }
        else{
            total[x] = total[x] - minimum;
            q.push(node(x,total[x]));
        }
    }
    temp.clear();
}
int main(){
 
    int ans,t=0,maximum,x,testcase,r,i,j,sum,y;
 //   freopen("output.txt","w",stdout);
   // freopen("input.txt","r",stdin);
    scanf("%d",&testcase);
    gets(str);
    gets(str);
    while( testcase-- ){
        if( t == 1){
            printf("\n");
        }
        t = 1;
        for( i = 1; i <= 26; i++){
            edge[i].clear();
            prereq[i] = 0;
        }
 
        while(gets(str)){
            r = strlen(str);
            if( r == 0){
                break;
            }
            x = str[0]-'A';
            x = x + 1;
            sum = 0;
            i = 2;
            while( i < r && str[i] != ' '){
                sum = (sum*10) + str[i]-'0';
                i++;
            }
            total[x] = sum;
            if( i == r){
                q.push(node(x,sum));
            }
            i++;
 
            for(; i < r; i++){
                y = str[i]-'A';
                y++;
                edge[y].push_back(x);
                prereq[x]++;
            }
        }
        ans = 0;
        while(!q.empty()){
            maximum = 0;
            res.clear();
            while( !q.empty() ){
                node top = q.top();
                q.pop();
                maximum = top.day;
                res.push_back(top.n);
            }
            ans = ans + maximum;
            for( i = 1; i <= 26; i++){
                check[i].clear();
            }
            for( i = 0; i < res.size(); i++){
                x = res[i];
                dfs(x,maximum);
            }
        }
        printf("%d\n",ans);
    }
return 0;
}

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0cmluZz4KI2luY2x1ZGU8Y3N0cmluZz4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxjc3RkbGliPgojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8Y21hdGg+CiNpbmNsdWRlPHF1ZXVlPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpzdHJ1Y3Qgbm9kZXsKICAgIGludCBuOwogICAgaW50IGRheTsKICAgIG5vZGUoaW50IGEsIGludCBiKXsKICAgICAgICBuID0gYTsKICAgICAgICBkYXkgPSBiOwogICAgfQogICAgYm9vbCBvcGVyYXRvciAgPChjb25zdCBub2RlJiBwKWNvbnN0ewogICAgICAgIHJldHVybiBkYXkgPiBwLmRheTsKICAgIH0KfTsKY2hhciBzdHJbNTBdOwppbnQgcHJlcmVxWzI4XTsKaW50IHRvdGFsWzI4XTsKdmVjdG9yPGludD5jaGVja1syN107CnZlY3RvcjxpbnQ+cmVzOwp2ZWN0b3I8aW50PmVkZ2VbMjhdOwpwcmlvcml0eV9xdWV1ZTxub2RlPnE7CnZvaWQgZGZzKCBpbnQgcixpbnQgcmVzdCl7CgogICAgaW50IG1pbmltdW0seCxqLGkseTsKICAgIHZlY3RvcjxpbnQ+dGVtcDsKICAgIHRvdGFsW3JdID0gcmVzdCAtIHRvdGFsW3JdOwogICAgZm9yKCBpID0gMDsgaSA8IGVkZ2Vbcl0uc2l6ZSgpOyBpKyspewogICAgICAgIHggPSBlZGdlW3JdW2ldOwogICAgICAgIHByZXJlcVt4XS0tOwogICAgICAgIGlmKCBwcmVyZXFbeF0gPT0gMCl7CiAgICAgICAgICAgIHRlbXAucHVzaF9iYWNrKHgpOwogICAgICAgIH0KICAgICAgICBlbHNlewogICAgICAgICAgICBjaGVja1t4XS5wdXNoX2JhY2socik7CiAgICAgICAgfQogICAgfQogICAgbWluaW11bSA9IHRvdGFsW3JdOwogICAgZm9yKCBpID0gMDsgaSA8IHRlbXAuc2l6ZSgpOyBpKyspewogICAgICAgIHggPSB0ZW1wW2ldOwogICAgICAgIGZvciggaiA9IDA7IGogPCBjaGVja1t4XS5zaXplKCk7IGorKyl7CiAgICAgICAgICAgIHkgPSBjaGVja1t4XVtqXTsKICAgICAgICAgICAgaWYodG90YWxbeV0gPCBtaW5pbXVtICl7CiAgICAgICAgICAgICAgICBtaW5pbXVtID0gdG90YWxbeV07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgaWYoIHRvdGFsW3hdIDw9IG1pbmltdW0gKXsKICAgICAgICAgICAgZGZzKHgsbWluaW11bSk7CiAgICAgICAgfQogICAgICAgIGVsc2V7CiAgICAgICAgICAgIHRvdGFsW3hdID0gdG90YWxbeF0gLSBtaW5pbXVtOwogICAgICAgICAgICBxLnB1c2gobm9kZSh4LHRvdGFsW3hdKSk7CiAgICAgICAgfQogICAgfQogICAgdGVtcC5jbGVhcigpOwp9CmludCBtYWluKCl7CgogICAgaW50IGFucyx0PTAsbWF4aW11bSx4LHRlc3RjYXNlLHIsaSxqLHN1bSx5OwogLy8gICBmcmVvcGVuKCJvdXRwdXQudHh0IiwidyIsc3Rkb3V0KTsKICAgLy8gZnJlb3BlbigiaW5wdXQudHh0IiwiciIsc3RkaW4pOwogICAgc2NhbmYoIiVkIiwmdGVzdGNhc2UpOwogICAgZ2V0cyhzdHIpOwogICAgZ2V0cyhzdHIpOwogICAgd2hpbGUoIHRlc3RjYXNlLS0gKXsKICAgICAgICBpZiggdCA9PSAxKXsKICAgICAgICAgICAgcHJpbnRmKCJcbiIpOwogICAgICAgIH0KICAgICAgICB0ID0gMTsKICAgICAgICBmb3IoIGkgPSAxOyBpIDw9IDI2OyBpKyspewogICAgICAgICAgICBlZGdlW2ldLmNsZWFyKCk7CiAgICAgICAgICAgIHByZXJlcVtpXSA9IDA7CiAgICAgICAgfQoKICAgICAgICB3aGlsZShnZXRzKHN0cikpewogICAgICAgICAgICByID0gc3RybGVuKHN0cik7CiAgICAgICAgICAgIGlmKCByID09IDApewogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgeCA9IHN0clswXS0nQSc7CiAgICAgICAgICAgIHggPSB4ICsgMTsKICAgICAgICAgICAgc3VtID0gMDsKICAgICAgICAgICAgaSA9IDI7CiAgICAgICAgICAgIHdoaWxlKCBpIDwgciAmJiBzdHJbaV0gIT0gJyAnKXsKICAgICAgICAgICAgICAgIHN1bSA9IChzdW0qMTApICsgc3RyW2ldLScwJzsKICAgICAgICAgICAgICAgIGkrKzsKICAgICAgICAgICAgfQogICAgICAgICAgICB0b3RhbFt4XSA9IHN1bTsKICAgICAgICAgICAgaWYoIGkgPT0gcil7CiAgICAgICAgICAgICAgICBxLnB1c2gobm9kZSh4LHN1bSkpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGkrKzsKCiAgICAgICAgICAgIGZvcig7IGkgPCByOyBpKyspewogICAgICAgICAgICAgICAgeSA9IHN0cltpXS0nQSc7CiAgICAgICAgICAgICAgICB5Kys7CiAgICAgICAgICAgICAgICBlZGdlW3ldLnB1c2hfYmFjayh4KTsKICAgICAgICAgICAgICAgIHByZXJlcVt4XSsrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGFucyA9IDA7CiAgICAgICAgd2hpbGUoIXEuZW1wdHkoKSl7CiAgICAgICAgICAgIG1heGltdW0gPSAwOwogICAgICAgICAgICByZXMuY2xlYXIoKTsKICAgICAgICAgICAgd2hpbGUoICFxLmVtcHR5KCkgKXsKICAgICAgICAgICAgICAgIG5vZGUgdG9wID0gcS50b3AoKTsKICAgICAgICAgICAgICAgIHEucG9wKCk7CiAgICAgICAgICAgICAgICBtYXhpbXVtID0gdG9wLmRheTsKICAgICAgICAgICAgICAgIHJlcy5wdXNoX2JhY2sodG9wLm4pOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGFucyA9IGFucyArIG1heGltdW07CiAgICAgICAgICAgIGZvciggaSA9IDE7IGkgPD0gMjY7IGkrKyl7CiAgICAgICAgICAgICAgICBjaGVja1tpXS5jbGVhcigpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGZvciggaSA9IDA7IGkgPCByZXMuc2l6ZSgpOyBpKyspewogICAgICAgICAgICAgICAgeCA9IHJlc1tpXTsKICAgICAgICAgICAgICAgIGRmcyh4LG1heGltdW0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHByaW50ZigiJWRcbiIsYW5zKTsKICAgIH0KcmV0dXJuIDA7Cn0K

Runtime error #stdin #stdout 0.01s 3420KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/ZXxfQy

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language