oj.uz

답안 #1088421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088421 2024-09-14T10:58:34 Z Rolo678 Aesthetic (NOI20_aesthetic) C++14
0 / 100
 313 ms 43096 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<pair<int,int>>>g(3e5+5);
vector<long long>dp2(3e5+5,-1);
 vector<long long>dp(3e5+5,-1);

signed main()
{
   // freopen("5-10.in", "r", stdin);

  int n,m;
  cin >> n>>m;
 // cin >> n >> m;
  vector<pair<int,int>>e(m+1);
  for(int i = 1;i<=m;i++)
  {
    int a,b,w;
    cin >> a >> b >> w;
    //cout << 'o';
    g[a].push_back({b,i});
    g[b].push_back({a,i});
    e[i] = {a,b};
//cout << 'o';
  }

  //dfs();
  dp[1] =0;
  queue<int>q;
  q.push(1);
  while(!q.empty())
  {
   int v = q.front();
    q.pop();
    for(auto u : g[v])
    {
      if(dp[u.first] == -1)
      {
        q.push(u.first);
        dp[u.first] = dp[v] + 1;
      }
    }
  }
    dp2[n] =0;
  //queue<int>q;
  q.push(n);
  while(!q.empty())
  {
    int v = q.front();
    q.pop();
    for(auto u : g[v])
    {
      if(dp2[u.first] == -1)
      {
        q.push(u.first);
        dp2[u.first] = dp2[v] + 1;
      }
    }
  }
  int mn = 1e9+5;
  int num = 0;
  int mn2 = 1e9+5;
  map<int,int>mp;
  int s =1;
  for(int i = 1;i<=m;i++)
  {
    int u = e[i].first;
    int v = e[i].second;

    if(dp[u] + dp2[v]+1 == dp[n])
    {
       mp[dp[u]]++;

       //cout << 'u';
    }
     if(dp[v] + dp2[u]+1 == dp[n])
    {
       mp[dp[v]]++;

       //cout << 'u';
    }
     /*/if(i==m && (dp[u] + dp2[v]+1 <mn+mn2+1))
    {
      num++;
       s= 0;
    }/*/
   // cout <<  dp[i.first] + dp2[i.second]+1 << '\n';
  }
  for(int i = 1;i<dp[n];i++)
  {
      if(mp[i]==1)num=1;
  }
   cout << dp[n] + ((num ==1));
}

Compilation message

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:60:7: warning: unused variable 'mn' [-Wunused-variable]
   60 |   int mn = 1e9+5;
      |       ^~
Aesthetic.cpp:62:7: warning: unused variable 'mn2' [-Wunused-variable]
   62 |   int mn2 = 1e9+5;
      |       ^~~
Aesthetic.cpp:64:7: warning: unused variable 's' [-Wunused-variable]
   64 |   int s =1;
      |       ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 301 ms 38064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 313 ms 38444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 36432 KB Output is correct
2 Correct 182 ms 34336 KB Output is correct
3 Correct 184 ms 35416 KB Output is correct
4 Correct 196 ms 35432 KB Output is correct
5 Correct 208 ms 35412 KB Output is correct
6 Correct 188 ms 35668 KB Output is correct
7 Correct 192 ms 35408 KB Output is correct
8 Correct 200 ms 35376 KB Output is correct
9 Correct 193 ms 35412 KB Output is correct
10 Correct 217 ms 35668 KB Output is correct
11 Correct 217 ms 35408 KB Output is correct
12 Correct 282 ms 36948 KB Output is correct
13 Correct 200 ms 35856 KB Output is correct
14 Correct 209 ms 43096 KB Output is correct
15 Correct 192 ms 42996 KB Output is correct
16 Correct 255 ms 37968 KB Output is correct
17 Incorrect 229 ms 37240 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 36432 KB Output is correct
2 Correct 182 ms 34336 KB Output is correct
3 Correct 184 ms 35416 KB Output is correct
4 Correct 196 ms 35432 KB Output is correct
5 Correct 208 ms 35412 KB Output is correct
6 Correct 188 ms 35668 KB Output is correct
7 Correct 192 ms 35408 KB Output is correct
8 Correct 200 ms 35376 KB Output is correct
9 Correct 193 ms 35412 KB Output is correct
10 Correct 217 ms 35668 KB Output is correct
11 Correct 217 ms 35408 KB Output is correct
12 Correct 282 ms 36948 KB Output is correct
13 Correct 200 ms 35856 KB Output is correct
14 Correct 209 ms 43096 KB Output is correct
15 Correct 192 ms 42996 KB Output is correct
16 Correct 255 ms 37968 KB Output is correct
17 Incorrect 229 ms 37240 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12124 KB Output isn't correct
2 Halted 0 ms 0 KB -