oj.uz

Submission #643175

# Submission time Handle Problem Language Result Execution time Memory
643175 2022-09-21T12:08:39 Z karrigan Robot (JOI21_ho_t4) C++14
0 / 100
 139 ms 28200 KB 
#include<bits/stdc++.h>
using namespace std;
const long long mx=1e18;
const int maxn=2e5+9;
int u[maxn];
int v[maxn];
int c[maxn];
long long p[maxn];
vector<int>fake[100001];
struct lena{
int v;
long long w;
bool operator < (const lena &p)const{
return w>p.w;
}
};
vector<lena>a[100001];
int cnt[maxn];
long long b[100001];
int use[100001];
priority_queue<lena>cc;
void sp(int u){
b[u]=0;
cc.push({u,0});
while (!cc.empty()){
    auto temp=cc.top();
    cc.pop();
    if (use[temp.v]==1)continue;
    use[temp.v]=1;
    for (auto v:a[temp.v]){
        if (b[v.v]>b[temp.v]+v.w){
            b[v.v]=b[temp.v]+v.w;
            cc.push({v.v,b[v.v]});
        }
    }
}
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>c[i]>>p[i];
        fake[u[i]].push_back(i);
        fake[v[i]].push_back(i);
    }
    for (int i=1;i<=n;i++){
        for (auto v1:fake[i]){
            cnt[c[v1]]++;
        }
        for (auto v1:fake[i]){
            if (cnt[c[v1]]==1){
                if (u[v1]!=i)a[i].push_back({u[v1],0});
                else a[i].push_back({v[v1],0});
            }
            else {
                if (u[v1]!=i)a[i].push_back({u[v1],p[v1]});
                else a[i].push_back({v[v1],p[v1]});
            }
        }
        for (auto v1:fake[i]){
            cnt[c[v1]]=0;
        }
    }
    for (int i=1;i<=n;i++){
        b[i]=1e18;
	}
	sp(1);
	if (b[n]==mx)cout<<-1;
	else cout<<b[n];

}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5036 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 5076 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 13724 KB Output is correct
2 Correct 25 ms 9036 KB Output is correct
3 Correct 70 ms 18856 KB Output is correct
4 Correct 34 ms 11088 KB Output is correct
5 Incorrect 139 ms 28200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5036 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 5076 KB Output isn't correct
8 Halted 0 ms 0 KB -