oj.uz

Submission #292922

# Submission time Handle Problem Language Result Execution time Memory
292922 2020-09-07T14:49:47 Z 문홍윤(#5817) Express 20/19 (ROI19_express) C++17
0 / 100
 743 ms 72952 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=4e16;

int sum, n, m, q, indeg[500010];
int topo[500010], re, fr;
LL p;

vector<pil> link[500010], rlink[500010];
vector<LL> dp[500010];
char str[500010];

void cl(int qu){
    re=fr=0;
    for(int i=1; i<=qu; i++)str[i]=0;
}

void merge_dp(int num){
    int sz=rlink[num].size();
    LL st=0;
    vector<int> pv(sz);
    vector<LL> tmp;
    while(1){
        LL minn=LLINF;
        int minnum=-1;
        for(int i=0; i<pv.size(); i++){
            int nw=rlink[num][i].F;
            LL c=rlink[num][i].S;
            if(pv[i]==dp[nw].size())continue;
            if(minn>dp[nw][pv[i]]+c){
                minn=dp[nw][pv[i]]+c;
                minnum=i;
            }
        }
        if(minnum==-1)break;
        if(st*p/(p-1)<minn){
            tmp.eb(minn);
            tmp.eb(minn);
            st=minn;
        }
        else tmp[tmp.size()-1]=minn;
        pv[minnum]++;
    }
    press(tmp);
    dp[num].resize(tmp.size());
    for(int i=0; i<tmp.size(); i++)dp[num][i]=tmp[i];
}

void solve(){
    scanf("%d %d %d %lld", &n, &m, &q, &p);
    for(int i=1; i<=m; i++){
        int a, b; LL c;
        scanf("%d %d %lld", &a, &b, &c);
        a+=sum, b+=sum;
        link[a].eb(b, c);
        rlink[b].eb(a, c);
        indeg[b]++;
    }
    for(int i=1; i<=n; i++){
        if(!indeg[i])topo[++re]=i;
    }
    for(fr=1; fr<=re; fr++){
        for(auto i:link[topo[fr]]){
            indeg[i.F]--;
            if(!indeg[i.F])topo[++re]=i.F;
        }
    }
    dp[1].eb(0);
    for(int i=2; i<=n; i++)merge_dp(topo[i]);
    for(int i=1; i<=q; i++){
        int a; LL s, e;
        scanf("%d %lld", &a, &s);
        a+=sum;
        e=s*p/(p-1);
        int num=upper_bound(all(dp[a]), e)-lower_bound(all(dp[a]), s);
        if(num)str[i]='1';
        else str[i]='0';
    }
    sum+=n;
    printf("%s\n", str+1);
    cl(q);
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--)solve();
}

Compilation message

express.cpp: In function 'void merge_dp(int)':
express.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=0; i<pv.size(); i++){
      |                      ~^~~~~~~~~~
express.cpp:42:21: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if(pv[i]==dp[nw].size())continue;
express.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0; i<tmp.size(); i++)dp[num][i]=tmp[i];
      |                  ~^~~~~~~~~~~
express.cpp: In function 'void solve()':
express.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |     scanf("%d %d %d %lld", &n, &m, &q, &p);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
express.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |         scanf("%d %d %lld", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
express.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |         scanf("%d %lld", &a, &s);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
express.cpp: In function 'int main()':
express.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 35584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35584 KB Output is correct
2 Correct 25 ms 35712 KB Output is correct
3 Correct 24 ms 35584 KB Output is correct
4 Correct 24 ms 35584 KB Output is correct
5 Correct 25 ms 35584 KB Output is correct
6 Correct 25 ms 35584 KB Output is correct
7 Correct 24 ms 35584 KB Output is correct
8 Correct 24 ms 35584 KB Output is correct
9 Correct 24 ms 35584 KB Output is correct
10 Incorrect 30 ms 35840 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35584 KB Output is correct
2 Correct 743 ms 72952 KB Output is correct
3 Incorrect 564 ms 64060 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35584 KB Output is correct
2 Correct 743 ms 72952 KB Output is correct
3 Incorrect 564 ms 64060 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35584 KB Output is correct
2 Correct 24 ms 35584 KB Output is correct
3 Correct 25 ms 35584 KB Output is correct
4 Correct 29 ms 35712 KB Output is correct
5 Correct 25 ms 35576 KB Output is correct
6 Correct 27 ms 35712 KB Output is correct
7 Correct 26 ms 35584 KB Output is correct
8 Correct 29 ms 36600 KB Output is correct
9 Incorrect 27 ms 35712 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35584 KB Output is correct
2 Correct 24 ms 35584 KB Output is correct
3 Correct 25 ms 35584 KB Output is correct
4 Correct 29 ms 35712 KB Output is correct
5 Correct 25 ms 35576 KB Output is correct
6 Correct 27 ms 35712 KB Output is correct
7 Correct 26 ms 35584 KB Output is correct
8 Correct 29 ms 36600 KB Output is correct
9 Incorrect 27 ms 35712 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 35584 KB Output isn't correct
2 Halted 0 ms 0 KB -