oj.uz

답안 #237092

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237092 2020-06-04T14:14:54 Z Autoratch 악어의 지하 도시 (IOI11_crocodile) C++14
46 / 100
 154 ms 262144 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int> 

const int N = 1e5 + 1;

vector<pair<int,int> > adj[N];
vector<int> ep;
priority_queue<pii,vector<pii>,greater<pii> > q;
int dist[N];
bool visited[N];

int dfs(int u,int p)
{
    if(dist[u]==0) return 0;
    int mn = INT_MAX,mn2 = INT_MAX;
    int m,m2;
    for(auto [d,v] : adj[u]) if(v!=p)
    {
        int each = dfs(v,u)+d;
        if(each<mn) mn2 = mn,m2 = m,mn = each,m = v;
        else if(each<mn2) mn2 = each,m2 = v;
    }
    return mn2;
}

int travel_plan(int n,int m,int r[][2],int l[],int k,int p[])
{
    for(int i = 0;i < m;i++)
    {
        int a = r[i][0],b = r[i][1],d = l[i];
        adj[a].push_back({d,b});
        adj[b].push_back({d,a});
    }
    for(int i = 0;i < k;i++) ep.push_back(p[i]);
    for(int i = 0;i < n;i++) dist[i] = INT_MAX;
    for(int x : ep) dist[x] = 0,q.push({0,x});
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(visited[u]) continue;
        visited[u] = true;
        for(auto [d,v] : adj[u]) if(dist[u]+d<dist[v]) dist[v] = dist[u]+d,q.push({dist[v],v});
    }
    return dfs(0,0);
}

Compilation message

crocodile.cpp: In function 'int dfs(int, int)':
crocodile.cpp:19:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [d,v] : adj[u]) if(v!=p)
              ^
crocodile.cpp:18:11: warning: variable 'm2' set but not used [-Wunused-but-set-variable]
     int m,m2;
           ^~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:45:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for(auto [d,v] : adj[u]) if(dist[u]+d<dist[v]) dist[v] = dist[u]+d,q.push({dist[v],v});
                  ^

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 7 ms 2688 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 7 ms 2688 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Runtime error 154 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 7 ms 2688 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Runtime error 154 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -