Submission #153164

#	Time	Username	Problem	Language	Result	Execution time	Memory
153164		Swan	Paths (BOI18_paths)	C++14	100 / 100	489 ms	97804 KiB

paths

#include <bits/stdc++.h>
#define stop system("pause")
#define INP freopen("input.txt","r",stdin)
#define OUTP freopen("solve1.txt","w",stdout)
#define int long long
using namespace std;

typedef long long ll;

vector<vector<int> > v;
const int maxn = 4e5;
int color[maxn];
int cnt[maxn][(1<<5)];
int n,m,k;

struct st{
    int mask;
    int sz;
    bool operator<(st b)const{
        return sz < b.sz;
    }
    st(int a,int b){
        mask = a;
        sz = b;
    }
};

int get_cnt(int x){
    int res = 0;
    while(x){
        res+=x%2;
        x/=2;
    }
    return res;
}

bool check(int mask,int x){
    return (mask&(1<<x));
}

void print_mask(int mask){
    for(int i(0) ; i < 5;i++){
        if(mask&(1<<i))cout << i+1 << ' ';
    }
    cout << endl;
}

void solve(int mask){
    for(int i(0); i < n;i++){
        if(!check(mask,color[i]))continue;
        int wout = mask^(1<<color[i]);
        //if(i == 0 && mask == 3)print_mask(wout);
        for(int j(0);j < v[i].size();j++){
            int to = v[i][j];
            //if(i == 0 && mask == 3)cout <<mask << ' ' << wout << ' ' << cnt[to][wout] << endl;
            cnt[i][mask]+=cnt[to][wout];
        }
    }
}

main()
{
    ios_base::sync_with_stdio(0);
    cin >> n >> m >> k;
    v.resize(n+2);
    for(int i(0); i < n;i++){
        cin >> color[i];
        color[i]--;
        //if(i == 1)cout << (1<<color[i]) << endl;
        cnt[i][1<<color[i]]++;
    }
    for(int i(0); i < m;i++){
        int a,b; cin >> a >> b;
        a--;b--;
        if(color[a] == color[b])continue;
        //cout << "good " << a+1 << ' ' << b+1 << endl;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vector<st> qwe;
    for(int i(0); i < (1<<k);i++){
        if(get_cnt(i) == 1)continue;
        qwe.push_back({i,get_cnt(i)});
    }
    sort(qwe.begin(),qwe.end());
    //cout << "w " << cnt[1][2] << endl;
    for(int i(0); i < qwe.size();i++){
        solve(qwe[i].mask);
    }
    int ans = 0;
    for(int i(0); i < n;i++){
        for(int j(0); j < qwe.size();j++){
            ans+=cnt[i][qwe[j].mask];
            /*if(i == 0){
                cout << qwe[j].mask << ' ' << cnt[i][qwe[j].mask] << " = ";
                print_mask(qwe[j].mask);
                cout << endl;
            }*/
        }
    }
    cout << ans;
    return 0;
}
/*
*/

Compilation message (stderr)

paths.cpp: In function 'void solve(long long int)':
paths.cpp:53:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j(0);j < v[i].size();j++){
                      ~~^~~~~~~~~~~~~
paths.cpp: At global scope:
paths.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
paths.cpp: In function 'int main()':
paths.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < qwe.size();i++){
                   ~~^~~~~~~~~~~~
paths.cpp:92:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j(0); j < qwe.size();j++){
                       ~~^~~~~~~~~~~~

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