oj.uz

Submission #284294

# Submission time Handle Problem Language Result Execution time Memory
284294 2020-08-27T07:43:34 Z 최은수(#5747) Aesthetic (NOI20_aesthetic) C++17
7 / 100
 2000 ms 1048580 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
ll w[300010];
vector<pi>adj[300010];
int pa[300010],pai[300010];
int dep[300010];
void dfs(int x,int p)
{
    dep[x]=dep[p]+1;
    for(pi&t:adj[x])
    {
        if(t.fi==p)
            pa[x]=t.fi,pai[x]=t.se;
        else
            dfs(t.fi,x);
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v>>w[i];
        adj[u].eb(v,i);
        adj[v].eb(u,i);
    }
    dfs(1,0);
    int l=1,r=n;
    int imn=n;
    ll ws=0;
    while(l!=r)
    {
        if(dep[l]>dep[r])
            ws+=w[pai[l]],imn=min(imn,pai[l]),l=pa[l];
        else
            ws+=w[pai[r]],imn=min(imn,pai[r]),r=pa[r];
    }
    ll mx=0;
    for(int i=m-1;i>imn;i--)
        mx=max(mx,w[i]);
    cout<<(ws+mx)<<endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 743 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 743 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 28768 KB Output is correct
2 Correct 320 ms 31224 KB Output is correct
3 Correct 319 ms 30872 KB Output is correct
4 Correct 378 ms 30784 KB Output is correct
5 Correct 371 ms 30968 KB Output is correct
6 Correct 371 ms 31584 KB Output is correct
7 Correct 346 ms 31412 KB Output is correct
8 Correct 333 ms 31480 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 29560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1193 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1193 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 743 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -