oj.uz

Submission #1088419

# Submission time Handle Problem Language Result Execution time Memory
1088419 2024-09-14T10:57:02 Z Rolo678 Aesthetic (NOI20_aesthetic) C++14
0 / 100
 307 ms 43092 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(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 6 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 6 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 307 ms 39300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 37212 KB Output is correct
2 Correct 173 ms 34976 KB Output is correct
3 Correct 179 ms 36140 KB Output is correct
4 Correct 180 ms 36244 KB Output is correct
5 Correct 189 ms 36176 KB Output is correct
6 Correct 199 ms 36188 KB Output is correct
7 Correct 188 ms 36100 KB Output is correct
8 Correct 207 ms 36176 KB Output is correct
9 Correct 184 ms 36176 KB Output is correct
10 Correct 181 ms 36336 KB Output is correct
11 Correct 209 ms 36180 KB Output is correct
12 Correct 216 ms 37712 KB Output is correct
13 Correct 179 ms 36180 KB Output is correct
14 Correct 184 ms 43092 KB Output is correct
15 Incorrect 168 ms 43020 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 37212 KB Output is correct
2 Correct 173 ms 34976 KB Output is correct
3 Correct 179 ms 36140 KB Output is correct
4 Correct 180 ms 36244 KB Output is correct
5 Correct 189 ms 36176 KB Output is correct
6 Correct 199 ms 36188 KB Output is correct
7 Correct 188 ms 36100 KB Output is correct
8 Correct 207 ms 36176 KB Output is correct
9 Correct 184 ms 36176 KB Output is correct
10 Correct 181 ms 36336 KB Output is correct
11 Correct 209 ms 36180 KB Output is correct
12 Correct 216 ms 37712 KB Output is correct
13 Correct 179 ms 36180 KB Output is correct
14 Correct 184 ms 43092 KB Output is correct
15 Incorrect 168 ms 43020 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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