Submission #124531

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
124531	2019-07-03 13:28:01	TadijaSebez	Bridges (APIO19_bridges)	C++11	100 / 100	2748 ms	49156 KiB

bridges

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int B=1050;
int w[N],u[N],v[N];
bool ban[N];
int t[N],b[N],c[N];
vector<int> use[B];
struct DSU
{
  int p[N],sz[N];
  void init(){ for(int i=0;i<N;i++) p[i]=i,sz[i]=1;}
  void init(int n){ for(int i=1;i<=n;i++) p[i]=i,sz[i]=1;}
  DSU(){ init();}
  int Find(int u){ return u==p[u]?u:Find(p[u]);}
  stack<int> was;
  void Union(int u, int v)
  {
    u=Find(u);
    v=Find(v);
    if(u==v){ was.push(0);return;}
    if(sz[u]>sz[v])
    {
      p[v]=u;
      sz[u]+=sz[v];
      was.push(v);
    }
    else
    {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<bn.size();j++) if(w[bn[j]]>=c[i]) use[i-l].pb(bn[j]);
                 ~^~~~~~~~~~
bridges.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0,j=0;i<qs.size();i++)
                   ~^~~~~~~~~~
bridges.cpp:83:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j<id.size() && w[id[j]]>=c[qs[i]])
          ~^~~~~~~~~~
bridges.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<use[qs[i]-l].size();k++)
                ~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:94:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<use[qs[i]-l].size();k++) DS.Undo();
                ~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:53:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i %i %i",&u[i],&v[i],&w[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:55:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<q;i++) scanf("%i %i %i",&t[i],&b[i],&c[i]);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27