Submission #107059

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
107059	2019-04-21 15:50:02	Pajaraja	Pipes (BOI13_pipes)	C++17	74.07 / 100	389 ms	24436 KiB

pipes

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>
#define MAXN 100007
#define MAXM 500007
using namespace std;
map<pair<int,int>,long long> mp;
vector<int> g[MAXN],c;
int gr[MAXM][2],n,m,deg[MAXN],parc[MAXN];
long long t[MAXN];
bool vi[MAXN];
void dfs(int s)
{
  c.push_back(s);
  vi[s]=true;
  for(int i=0;i<g[s].size();i++) if(!vi[g[s][i]]) dfs(g[s][i]);
}
int main()
{
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++) scanf("%lld",&t[i]);
  for(int i=0;i<m;i++) 
  {
    scanf("%d%d",&gr[i][0],&gr[i][1]);
    g[gr[i][0]].push_back(gr[i][1]);
    g[gr[i][1]].push_back(gr[i][0]);
  }
  queue<int> q;
  for(int i=1;i<=n;i++) deg[i]=g[i].size();
  for(int i=1;i<=n;i++) if(deg[i]==1) q.push(i);
  while(!q.empty())
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int)':
pipes.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(!vi[g[s][i]]) dfs(g[s][i]);
              ~^~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[u].size();i++) if(!vi[g[u][i]]) 
               ~^~~~~~~~~~~~
pipes.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<c.size();i++) tz+=t[i];
               ~^~~~~~~~~
pipes.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=2;i<c.size();i+=2) parc[i]=parc[i-2]+t[c[i-2]];
               ~^~~~~~~~~
pipes.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=3;i<c.size();i+=2) parc[i]=parc[i-2]+t[c[i-2]];
               ~^~~~~~~~~
pipes.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<c.size()-1;i++) mp[make_pair(c[i],c[i+1])]=mp[make_pair(c[i+1],c[i])]=2*(parc[i+1]-parc[i]);
               ~^~~~~~~~~~~
pipes.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
pipes.cpp:20:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%lld",&t[i]);
                        ~~~~~^~~~~~~~~~~~~~
pipes.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&gr[i][0],&gr[i][1]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 44.074074074074076 / 70