Submission #1025928


Source Code Expand

#include <cmath>
#include <queue>
#include <cstdio>
#include <map>
#include <vector>
#include <iostream>
#include <stack>
#include <climits>
#include <set>
#include <queue>
#include <algorithm>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;


typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int N = 100001;
const int MOD = 1e9 + 7;

bool pairCompare(const std::pair<int,pair<int,int>>& firstElem, const std::pair<int,pair<int,int>>& secondElem) {
    return firstElem.first < secondElem.first;
    
}

void initialize(int size[], int Arr[ ], int N)
{
    for(int i = 0;i<N;i++)
    {
        Arr[ i ] = i ;
        size[ i ] = 1;
    }
}

int root (int Arr[ ] ,int i)
{
    while(Arr[ i ] != i)
    {
        Arr[ i ] = Arr[ Arr[ i ] ] ;
        i = Arr[ i ];
    }
    return i;
}

/*modified union function where we connect the elements by changing the root of one of the element */
/*
 void unio(int Arr[ ] ,int A ,int B)
 {
 int root_A = root(Arr, A);
 int root_B = root(Arr, B);
 Arr[ root_A ] = root_B ;       //setting parent of root(A) as root(B).
 }
 */

void weightedunio(int Arr[ ],int size[ ],int A,int B)
{
    int root_A = root(Arr, A);
    int root_B = root(Arr, B);
    if(size[root_A] < size[root_B ])
    {
        Arr[ root_A ] = Arr[root_B];
        size[root_B] += size[root_A];
    }
    else
    {
        Arr[ root_B ] = Arr[root_A];
        size[root_A] += size[root_B];
    }
    
}

bool find(int Arr[], int A,int B)
{
    if( root(Arr, A)==root(Arr, B) )       //if A and B have same root,means they are connected.
        return true;
    else
        return false;
}



int main(int argc, const char * argv[]) {
    
    
    int n, m;
    cin>>n>>m;
    vector<pair<int,pair<int,int>>> adj;
    for(int i = 0; i < m; i++){
        int a,b,c;
        cin>>a>>b>>c; a--; b--;
        adj.push_back(mp(c,mp(a,b)));
    }
    
    
    
    int q;
    cin>>q;
    for(int i = 0; i < q; i++){
        int s,t;
        cin>>s>>t;s--;t--;
        adj.push_back(mp(0,mp(s,t)));
        sort(adj.begin(), adj.end(), pairCompare);
        
        int ans = 0;
        
       
        
        int size[n], arr[n];
        initialize(size, arr, n);
        
        for(int i = 0; i <= m; i++){
            if(!find(arr, adj[i].second.first, adj[i].second.second)){
                ans += adj[i].first;
                weightedunio(arr,size,adj[i].second.first, adj[i].second.second);
            }
        }
        
        cout<<ans<<endl;
        
    }
    
    /*
     4 3
     1 2 3
     2 3 4
     3 4 5
     1
     2 3*/
    
    return 0;
}

Submission Info

Submission Time
Task A - Graph
User titanlord89
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2977 Byte
Status WA
Exec Time 3154 ms
Memory 6512 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 300 0 / 200
Status
AC × 1
WA × 1
AC × 2
WA × 10
AC × 2
WA × 12
TLE × 7
AC × 2
WA × 12
TLE × 15
Set Name Test Cases
Sample sample_1.txt, sample_2.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt
All sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt
Case Name Status Exec Time Memory
sample_1.txt WA 2 ms 256 KB
sample_2.txt AC 3 ms 256 KB
subtask_1_1.txt WA 3 ms 256 KB
subtask_1_10.txt WA 202 ms 3444 KB
subtask_1_11.txt AC 3 ms 256 KB
subtask_1_2.txt WA 43 ms 1148 KB
subtask_1_3.txt WA 401 ms 6512 KB
subtask_1_4.txt WA 6 ms 384 KB
subtask_1_5.txt WA 8 ms 384 KB
subtask_1_6.txt WA 101 ms 1912 KB
subtask_1_7.txt WA 402 ms 6512 KB
subtask_1_8.txt WA 7 ms 384 KB
subtask_1_9.txt WA 13 ms 576 KB
subtask_2_1.txt TLE 3154 ms 6512 KB
subtask_2_2.txt TLE 3154 ms 6512 KB
subtask_2_3.txt TLE 3154 ms 6512 KB
subtask_2_4.txt TLE 3154 ms 6512 KB
subtask_2_5.txt WA 1913 ms 512 KB
subtask_2_6.txt TLE 3154 ms 704 KB
subtask_2_7.txt TLE 3154 ms 1912 KB
subtask_2_8.txt TLE 3154 ms 6512 KB
subtask_3_1.txt TLE 3154 ms 6512 KB
subtask_3_2.txt TLE 3154 ms 6512 KB
subtask_3_3.txt TLE 3154 ms 640 KB
subtask_3_4.txt TLE 3154 ms 576 KB
subtask_3_5.txt TLE 3154 ms 3444 KB
subtask_3_6.txt TLE 3154 ms 6512 KB
subtask_3_7.txt TLE 3154 ms 6512 KB
subtask_3_8.txt TLE 3154 ms 6512 KB