oj.uz

Submission #1088433

# Submission time Handle Problem Language Result Execution time Memory
1088433 2024-09-14T11:10:19 Z Rolo678 Aesthetic (NOI20_aesthetic) C++14
16 / 100
 449 ms 43088 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]]++;
       if(i==m)mp[dp[u]]++;
       //cout << 'u';
    }
     if(dp[v] + dp2[u]+1 == dp[n])
    {
       mp[dp[v]]++;
       if(mp[dp[v] ]== mp[dp[u]])mp[dp[v]]--;
       if(i==m)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 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 312 ms 39508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 37204 KB Output is correct
2 Correct 196 ms 35152 KB Output is correct
3 Correct 187 ms 36172 KB Output is correct
4 Correct 188 ms 35920 KB Output is correct
5 Correct 190 ms 35956 KB Output is correct
6 Correct 193 ms 35920 KB Output is correct
7 Correct 196 ms 35988 KB Output is correct
8 Correct 225 ms 35920 KB Output is correct
9 Correct 196 ms 35960 KB Output is correct
10 Correct 202 ms 36180 KB Output is correct
11 Correct 196 ms 36116 KB Output is correct
12 Correct 216 ms 37412 KB Output is correct
13 Correct 195 ms 36176 KB Output is correct
14 Correct 233 ms 43088 KB Output is correct
15 Correct 218 ms 43088 KB Output is correct
16 Correct 223 ms 37716 KB Output is correct
17 Correct 224 ms 36892 KB Output is correct
18 Correct 254 ms 37456 KB Output is correct
19 Correct 190 ms 35156 KB Output is correct
20 Correct 179 ms 35156 KB Output is correct
21 Correct 192 ms 35124 KB Output is correct
22 Correct 193 ms 35152 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 37204 KB Output is correct
2 Correct 196 ms 35152 KB Output is correct
3 Correct 187 ms 36172 KB Output is correct
4 Correct 188 ms 35920 KB Output is correct
5 Correct 190 ms 35956 KB Output is correct
6 Correct 193 ms 35920 KB Output is correct
7 Correct 196 ms 35988 KB Output is correct
8 Correct 225 ms 35920 KB Output is correct
9 Correct 196 ms 35960 KB Output is correct
10 Correct 202 ms 36180 KB Output is correct
11 Correct 196 ms 36116 KB Output is correct
12 Correct 216 ms 37412 KB Output is correct
13 Correct 195 ms 36176 KB Output is correct
14 Correct 233 ms 43088 KB Output is correct
15 Correct 218 ms 43088 KB Output is correct
16 Correct 223 ms 37716 KB Output is correct
17 Correct 224 ms 36892 KB Output is correct
18 Correct 254 ms 37456 KB Output is correct
19 Correct 190 ms 35156 KB Output is correct
20 Correct 179 ms 35156 KB Output is correct
21 Correct 192 ms 35124 KB Output is correct
22 Correct 193 ms 35152 KB Output is correct
23 Incorrect 220 ms 37712 KB Output isn't correct
24 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 -