Submission #100242

#	Time	Username	Problem	Language	Result	Execution time	Memory
100242		shafinalam	Paths (BOI18_paths)	C++14	100 / 100	824 ms	169020 KiB

paths

#include <bits/stdc++.h>

using namespace std;

const int mx = 3e5+5;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<int,pii>piii;

#define  sf scanf
#define  pf printf

#define  input freopen("input.txt","r",stdin)
#define  output freopen("output.txt","w",stdout)

#define  inf 1e16
#define  ff first
#define  ss second
#define  MP make_pair
#define  pb push_back
#define  all(v) v.begin(), v.end()
#define  printcase(cases) printf("Case %d:", cases);
#define  Unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define  FAST  ios_base::sync_with_stdio(0);cout.tie(0)
#define  endl printf("\n")
#define  __lcm(a, b) ((a*b)/__gcd(a, b))

int  Set(int N,int pos){return N=N | (1<<pos);}
int  reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}

vector<int>adj[mx];
ll dp[mx][1<<6];
int arr[mx];

ll solve(int u, int mask)
{
    if(dp[u][mask]!=-1) return dp[u][mask];
    ll ans = 0;
    for(int i = 0; i < adj[u].size(); i++)
    {
        int v = adj[u][i];
        if(check(mask, arr[v])) continue;
        ans+=solve(v, Set(mask, arr[v]))+1;
    }
    return dp[u][mask] = ans;
}
int main()
{
    int n, m, k;
    sf("%d%d%d", &n, &m, &k);

    for(int i = 1; i <= n; i++) sf("%d", &arr[i]);
    while(m--)
    {
        int u, v;
        sf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    memset(dp, -1, sizeof dp);
    ll ans = 0, mask = 0;
    for(int i = 1; i <= n; i++) ans+=solve(i, Set(mask, arr[i]));
    pf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'll solve(int, int)':
paths.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++)
                    ~~^~~~~~~~~~~~~~~
paths.cpp: In function 'int main()':
paths.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     sf("%d%d%d", &n, &m, &k);
       ^
paths.cpp:55:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) sf("%d", &arr[i]);
                                   ^
paths.cpp:59:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         sf("%d%d", &u, &v);
           ^

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