oj.uz

답안 #910863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
910863 2024-01-18T08:35:51 Z ibm2006 다리 (APIO19_bridges) C++17
14 / 100
 82 ms 18860 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,m,q,e,ee,a[1100000],h[1100000],dep[1100000],ans[1100000];
vector<pair<pair<ll,ll>,pair<ll,ll>>> u;
pair<pair<ll,ll>,pair<ll,ll>> pq;
ll f(ll x)
{
    if(a[x]==x)
        return x;
    a[x]=f(a[x]);
    return a[x];
}
void g(ll x,ll y)
{
    x=f(x);
    y=f(y);
    if(x==y)
        return;
    if(dep[x]>dep[y])
        swap(x,y);
    dep[y]+=dep[x];
    a[x]=y;
}
int main()
{
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++)
    {
        a[i]=i;
        dep[i]=1;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&x,&y,&z);
        u.push_back({{-z,1},{x,y}});
    }
    scanf("%lld",&q);
    for(i=1;i<=q;i++)
    {
        scanf("%lld %lld %lld",&x,&y,&z);
        u.push_back({{-z,2},{i,y}});
    }
    sort(u.begin(),u.end());
    for(e=0;e<u.size();e++)
    {
        pq=u[e];
        if(pq.first.second==1)
        {
            x=pq.second.first;
            y=pq.second.second;
            g(x,y);
            continue;
        }
        x=pq.second.first;
        y=pq.second.second;
        ans[x]=dep[f(y)];
    }
    for(i=1;i<=q;i++)
    {
        printf("%lld\n",ans[i]);
    }
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:45:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(e=0;e<u.size();e++)
      |             ~^~~~~~~~~
bridges.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%lld %lld %lld",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%lld",&q);
      |     ~~~~~^~~~~~~~~~~
bridges.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%lld %lld %lld",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 16880 KB Output is correct
2 Correct 39 ms 12192 KB Output is correct
3 Correct 35 ms 9924 KB Output is correct
4 Correct 40 ms 10176 KB Output is correct
5 Correct 71 ms 16808 KB Output is correct
6 Correct 74 ms 18004 KB Output is correct
7 Correct 72 ms 17068 KB Output is correct
8 Correct 67 ms 17080 KB Output is correct
9 Correct 56 ms 17340 KB Output is correct
10 Correct 56 ms 16828 KB Output is correct
11 Correct 65 ms 17344 KB Output is correct
12 Correct 66 ms 17596 KB Output is correct
13 Correct 66 ms 17324 KB Output is correct
14 Correct 70 ms 17508 KB Output is correct
15 Correct 79 ms 17932 KB Output is correct
16 Correct 75 ms 18656 KB Output is correct
17 Correct 77 ms 18860 KB Output is correct
18 Correct 81 ms 17728 KB Output is correct
19 Correct 77 ms 17744 KB Output is correct
20 Correct 67 ms 18096 KB Output is correct
21 Correct 66 ms 17108 KB Output is correct
22 Correct 69 ms 18092 KB Output is correct
23 Correct 68 ms 16860 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

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