Submission #1111360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111360		salmon	Drivers (BOI24_drivers)	C++14	100 / 100	144 ms	11768 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int N;
int M;
int Q;
int parent[200100];
vector<pair<int,pair<int,int>>> edge;
int u,v,t;
vector<pair<pair<int,int>,pair<int,int>>> queries;
bool ans[200100];

int root(int i){
    if(parent[i] == i) return i;
    return parent[i] = root(parent[i]);
}

void connect(int a, int b){
    a = root(a);
    b = root(b);

    if(a == b) return;

    parent[a] = b;
}

int main(){

    scanf(" %d",&N);
    scanf(" %d",&M);
    scanf(" %d",&Q);

    for(int i = 1; i <= N; i++) parent[i] = i;

    for(int i = 0; i < M; i++){
        scanf(" %d",&u);
        scanf(" %d",&v);
        scanf(" %d",&t);

        edge.push_back({t,{u,v}});
    }

    sort(edge.begin(),edge.end());

    for(int i = 0; i < Q; i++){
        scanf(" %d",&u);
        scanf(" %d",&v);
        scanf(" %d",&t);

        queries.push_back({{t,i},{u,v}});
    }

    sort(queries.begin(),queries.end());

    int it = 0;
    for(int i = 0; i < Q; i++){
        while(it != edge.size() && edge[it].first <= queries[i].first.first){
            connect(edge[it].second.first,edge[it].second.second);
            it++;
        }

        ans[queries[i].first.second] = (root(queries[i].second.second) == root(queries[i].second.first));
    }

    for(int i = 0; i < Q; i++){
        if(ans[i]) printf("TAIP\n");
        else printf("NE\n");
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         while(it != edge.size() && edge[it].first <= queries[i].first.first){
      |               ~~~^~~~~~~~~~~~~~
Main.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
Main.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf(" %d",&Q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
Main.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf(" %d",&v);
      |         ~~~~~^~~~~~~~~~
Main.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf(" %d",&t);
      |         ~~~~~^~~~~~~~~~
Main.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
Main.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf(" %d",&v);
      |         ~~~~~^~~~~~~~~~
Main.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf(" %d",&t);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 45 / 45