oj.uz

Submission #182146

# Submission time Handle Problem Language Result Execution time Memory
182146 2020-01-09T12:04:53 Z Ruxandra985 Toll (BOI17_toll) C++14
7 / 100
 397 ms 111312 KB 
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
map <int,int> rmq[20][50010];
map <int , pair <int,int> > mp;
int lg[50010] , step[50010];
deque <pair <int,int> > dq;
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int k , n , m , o , x , y, z, i , j , p , len , elem , nod , nr , nrr;
    fscanf (fin,"%d%d%d%d",&k,&n,&m,&o);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d%d",&x,&y,&z);
        rmq[0][min(x , y)][max(x , y)] = z;
    }
    for (i=2;i<=n;i++)
        lg[i] = 1 + lg[i/2];
    for (p=1;(1<<p) <= n/k;p++){
        for (i=0;i<=n;i++){
            if (i / k + (1 << p) <= n / k){ /// e ok

                for (j = (i / k + (1 << p)) * k ; j < (i / k + (1 << p) + 1) * k; j++){
                        for (x = (i / k + (1 << (p-1))) * k ; x < (i / k + (1 << (p-1)) + 1) * k; x++){
                            if (rmq[p-1][i][x] && rmq[p-1][x][j]){
                                if (!rmq[p][i][j])
                                    rmq[p][i][j] = rmq[p-1][i][x] + rmq[p-1][x][j];
                                else rmq[p][i][j] = min(rmq[p][i][j] , rmq[p-1][i][x] + rmq[p-1][x][j]);
                            }
                        }
                }

            }
            else break;
        }
    }

    for (;o;o--){
        fscanf (fin,"%d%d",&x,&y);

        if (x / k == y / k){
            fprintf (fout,"-1");
            continue;
        }

        len = (y / k) - (x / k);
        elem = 0;
        while (len){

            step[++elem] = lg[len];

            len -= (1 << lg[len]);
        }
        dq.push_back(make_pair(x , 1));
        mp[x] = make_pair(o , 0); /// frecventa + cost sa ajungi
        while (!dq.empty()){

            nod = dq.front().first;
            nr = dq.front().second;
            nrr = step[nr];
            dq.pop_front();
            if (nr == elem+1)
                continue;
            mp[nod].first = -o;

            for (j = (nod / k + (1 << nrr)) * k ; j < (nod / k + (1 << nrr) + 1) * k; j++){
                if (rmq[nrr][nod][j] && ((mp[j].first != o && mp[j].first != -o)  || mp[j].second > mp[nod].second + rmq[nrr][nod][j])){
                    mp[j].second = mp[nod].second + rmq[nrr][nod][j];
                    if (mp[j].first != o){ /// nu e ACUM in deque
                        mp[j].first = o;
                        dq.push_back(make_pair(j , nr + 1));
                    }

                }
            }

        }
        if ((mp[y].first != o && mp[y].first != -o))
            fprintf (fout,"-1\n");
        else fprintf (fout,"%d\n",mp[y].second);

    }

    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:13:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d%d",&k,&n,&m,&o);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:15:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d%d",&x,&y,&z);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:40:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 84492 KB Output is correct
2 Correct 45 ms 47324 KB Output is correct
3 Correct 47 ms 47324 KB Output is correct
4 Correct 39 ms 47224 KB Output is correct
5 Correct 48 ms 47732 KB Output is correct
6 Correct 48 ms 47708 KB Output is correct
7 Correct 48 ms 47708 KB Output is correct
8 Correct 180 ms 81884 KB Output is correct
9 Correct 167 ms 81804 KB Output is correct
10 Correct 137 ms 80964 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 111312 KB Output is correct
2 Correct 46 ms 47456 KB Output is correct
3 Incorrect 45 ms 47324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47312 KB Output is correct
2 Incorrect 46 ms 47280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47312 KB Output is correct
2 Incorrect 46 ms 47280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 84492 KB Output is correct
2 Correct 45 ms 47324 KB Output is correct
3 Correct 47 ms 47324 KB Output is correct
4 Correct 39 ms 47224 KB Output is correct
5 Correct 48 ms 47732 KB Output is correct
6 Correct 48 ms 47708 KB Output is correct
7 Correct 48 ms 47708 KB Output is correct
8 Correct 180 ms 81884 KB Output is correct
9 Correct 167 ms 81804 KB Output is correct
10 Correct 137 ms 80964 KB Output is correct
11 Correct 397 ms 111312 KB Output is correct
12 Correct 46 ms 47456 KB Output is correct
13 Incorrect 45 ms 47324 KB Output isn't correct
14 Halted 0 ms 0 KB -