oj.uz

Submission #480342

# Submission time Handle Problem Language Result Execution time Memory
480342 2021-10-15T17:40:19 Z nicolaalexandra Restore Array (RMI19_restore) C++14
0 / 100
 600 ms 1032 KB 
#include <bits/stdc++.h>
#define DIM 10010
#define INF 2000000000
using namespace std;

vector <pair<int,int> > L[DIM];
deque <int> c;
int viz[DIM],sp[DIM];
int n,m,i,j,x,y,k,val;

void add_edge (int x, int y, int cost){
    L[x].push_back(make_pair(y,cost));
    //cout<<x<<" "<<y<<" "<<cost<<"\n";
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;

    for (i=1;i<=m;i++){
        cin>>x>>y>>k>>val;
        x++, y++;
        if (val)
            add_edge(x-1,y,k-1);
        else add_edge(y,x-1,-k);
    }

    for (i=1;i<=n;i++){
        add_edge(i-1,i,1);
        add_edge(i,i-1,0);
        sp[i] = INF;
    }

    c.push_back(0);
    viz[0] = 1;
    sp[0] = 1;

    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        viz[nod] = 0;

        for (auto it : L[nod]){
            int vecin = it.first, cost = it.second;

            if (sp[nod] + cost < sp[vecin]){
                sp[vecin] = sp[nod] + cost;
                if (!viz[vecin]){
                    viz[vecin] = 1;
                    c.push_back(vecin);
                }}}}

    for (i=1;i<=n;i++){
        if (sp[i] == sp[i-1])
            cout<<"1 ";
        else cout<<"0 ";
    }

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 532 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Execution timed out 1079 ms 460 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 844 KB Output is correct
2 Correct 10 ms 1032 KB Output is correct
3 Correct 11 ms 972 KB Output is correct
4 Correct 11 ms 1028 KB Output is correct
5 Execution timed out 1086 ms 924 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 844 KB Output is correct
2 Correct 10 ms 1032 KB Output is correct
3 Correct 11 ms 972 KB Output is correct
4 Correct 11 ms 1028 KB Output is correct
5 Execution timed out 1086 ms 924 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 532 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Execution timed out 1079 ms 460 KB Time limit exceeded
6 Halted 0 ms 0 KB -