Submission #252323

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
252323	2020-07-25 09:23:48	frodakcin	Space Pirate (JOI14_space_pirate)	C++11	100 / 100	390 ms	43508 KiB

space_pirate

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 <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
using ll = long long;
const int MN = 101000;
int N, a[MN], X[MN], Y[MN], L, _map[MN*2], *map=_map+MN, p[MN][17], s[MN];
ll K, f[MN], psum[MN*2];
bool vis[MN];
std::vector<int> b[MN], path, invmap[MN*2], invmap2[MN*2];
void dfs(int n)
{
  for(int i=0;p[n][i]&&p[p[n][i]][i];++i)
    p[n][i+1]=p[p[n][i]][i];
  vis[n]=1;
  s[n] = 1;
  for(auto x:b[n])
    if(vis[x])
    {
      assert(x==path.front());
      L=X[n];
      assert(path[L]==n);
    }
    else
    {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

space_pirate.cpp: In function 'void case2(int, int)':
space_pirate.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<q.size();++i) dfs(q[i], i);
              ~^~~~~~~~~
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:193:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<path.size();++i)
              ~^~~~~~~~~~~~
space_pirate.cpp:213:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(L<path.size())
     ~^~~~~~~~~~~~
space_pirate.cpp:217:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i+1<path.size();++i)
               ~~~^~~~~~~~~~~~
space_pirate.cpp:247:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(L<path.size()) for(int i=0;i<L;++i) s[path[i]]-=s[path[L]];
     ~^~~~~~~~~~~~
space_pirate.cpp:269:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(L<path.size()) for(int i=0;i<L;++i) s[path[i]]+=s[path[L]];
     ~^~~~~~~~~~~~
space_pirate.cpp:181:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~
space_pirate.cpp:182:40: 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("%d", a+i), b[a[i]].push_back(i);
                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 33 / 33
• Subtask 4: 20 / 20