Submission #446576

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
446576	2021-07-22 13:17:18	keta_tsimakuridze	Paths (BOI18_paths)	C++14	100 / 100	733 ms	79840 KiB

paths

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 f first
#define s second
#define ll long long
using namespace std;
const int N=3e5+5,mod=1e9+7;
int t,n,m,k,cnt[N],col[N];
vector<pair<int,ll> > en[34];
vector<int> V[N][6];
 main(){
  cin>>n>>m>>k;
  for(int i=1;i<=n;i++){
    cin>>col[i];
    col[i]--;
    V[0][col[i]].push_back(i);
  }
  for(int i=1;i<=m;i++) {
    int u,v;
    cin>>u>>v;
    V[u][col[v]].push_back(v);
    V[v][col[u]].push_back(u);
  }
  en[0].push_back({0,1});
  ll ans = -n;
  for(int i = 1; i<(1<<k); i++) {
    for(int j=1;j<=n;j++) cnt[j] = 0;
    for(int j=0;j<k;j++) {
      if(!((1<<j) & i)) continue;
      int b = i ^ (1<<j);
      for(int k=0; k<en[b].size(); k++){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

paths.cpp:10:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 |  main(){
      |  ^~~~
paths.cpp: In function 'int main()':
paths.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    for(int k=0; k<en[b].size(); k++){
      |                 ~^~~~~~~~~~~~~
paths.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int p=0; p<V[u][j].size(); p++) {
      |                  ~^~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30