oj.uz

Submission #1088421

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 301 ms 38064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 313 ms 38444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12124 KB Output isn't correct
2 Halted 0 ms 0 KB -