oj.uz

Submission #737012

# Submission time Handle Problem Language Result Execution time Memory
737012 2023-05-06T13:04:40 Z josanneo22 Paths (BOI18_paths) C++17
100 / 100
 174 ms 84844 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 


void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename A>
void __print(const A &x);
template <typename A, typename B>
void __print(const pair<A, B> &p);
template <typename... A>
void __print(const tuple<A...> &t);
template <typename T>
void __print(stack<T> s);
template <typename T>
void __print(queue<T> q);
template <typename T, typename... U>
void __print(priority_queue<T, U...> q);
template <typename A>
void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
template <typename A, typename B>
void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.first);
    cerr << ',';
    __print(p.second);
    cerr << ')';
}
template <typename... A>
void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first](const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
template <typename T>
void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
template <typename T>
void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
template <typename T, typename... U>
void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
void _print() { cerr << "]\n"; }
template <typename Head, typename... Tail>
void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T))
        cerr << ", ";
    _print(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "Line:" << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
#define debug(...)
#endif


#define int long long
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd()
{
	int s=0;
	char ch=getchar(),last;
	while(ch<'0'||ch>'9') last=ch,ch=getchar();
	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return last=='-'?-s:s;
}
int num[100];
inline void rt(int x)
{
	if(x<0) putchar('-'),x=-x;;
	int len=0;
	do num[len++]=x%10;while(x/=10);
	while(len--) putchar(num[len]+'0');
}
const int maxn=3e5+5;
vector<int> c(maxn),a(maxn),b(maxn);
int dp[maxn][32];
void solve(){
    int n=rd(),m=rd(),k=rd();
    for(int i=1;i<=n;i++){
        c[i]=rd();
        c[i]--;
        dp[i][(1<<c[i])]=1;
    }
    for(int i=1;i<=m;i++) a[i]=rd(),b[i]=rd();
    int ans=0;
    for(int bt=1;bt<(1<<k);bt++){//枚举每个不同的颜色路线
        if(__builtin_popcountll(bt) == 1) {//如果只有一个颜色就不对了
            continue;
        }
        for(int i=1;i<=m;i++){
            //如果c[i]有和bt一样的bit,我们就可以加上b[i][不同的bit]
            if(bt&(1<<c[a[i]])) dp[a[i]][bt]+=dp[b[i]][bt^(1<<c[a[i]])];
            //相同
            if(bt&(1<<c[b[i]])) dp[b[i]][bt]+=dp[a[i]][bt^(1<<c[b[i]])];
        }
        //加起来就是答案啦~
        for(int i=1;i<=n;i++) ans+=dp[i][bt];
    }
    rt(ans);
}
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	solve();
}

Compilation message

paths.cpp: In function 'long long int rd()':
paths.cpp:115:18: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |  return last=='-'?-s:s;
      |         ~~~~~~~~~^~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7404 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 3 ms 7304 KB Output is correct
4 Correct 4 ms 7400 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7400 KB Output is correct
7 Correct 3 ms 7396 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10964 KB Output is correct
2 Correct 21 ms 9912 KB Output is correct
3 Correct 89 ms 84764 KB Output is correct
4 Correct 21 ms 17212 KB Output is correct
5 Correct 15 ms 17132 KB Output is correct
6 Correct 67 ms 59780 KB Output is correct
7 Correct 90 ms 84844 KB Output is correct
8 Correct 95 ms 84828 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7404 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 3 ms 7304 KB Output is correct
4 Correct 4 ms 7400 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7400 KB Output is correct
7 Correct 3 ms 7396 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7396 KB Output is correct
11 Correct 27 ms 10964 KB Output is correct
12 Correct 21 ms 9912 KB Output is correct
13 Correct 89 ms 84764 KB Output is correct
14 Correct 21 ms 17212 KB Output is correct
15 Correct 15 ms 17132 KB Output is correct
16 Correct 67 ms 59780 KB Output is correct
17 Correct 90 ms 84844 KB Output is correct
18 Correct 95 ms 84828 KB Output is correct
19 Correct 25 ms 10956 KB Output is correct
20 Correct 21 ms 9812 KB Output is correct
21 Correct 85 ms 84824 KB Output is correct
22 Correct 21 ms 17108 KB Output is correct
23 Correct 18 ms 17108 KB Output is correct
24 Correct 81 ms 59784 KB Output is correct
25 Correct 85 ms 84824 KB Output is correct
26 Correct 94 ms 84824 KB Output is correct
27 Correct 54 ms 9812 KB Output is correct
28 Correct 66 ms 11700 KB Output is correct
29 Correct 162 ms 84824 KB Output is correct
30 Correct 124 ms 47268 KB Output is correct
31 Correct 127 ms 47264 KB Output is correct
32 Correct 174 ms 84764 KB Output is correct
33 Correct 3 ms 7380 KB Output is correct
34 Correct 4 ms 7380 KB Output is correct
35 Correct 3 ms 7380 KB Output is correct
36 Correct 3 ms 7404 KB Output is correct
37 Correct 3 ms 7400 KB Output is correct
38 Correct 3 ms 7380 KB Output is correct
39 Correct 3 ms 7380 KB Output is correct
40 Correct 3 ms 7380 KB Output is correct
41 Correct 3 ms 7384 KB Output is correct
42 Correct 3 ms 7380 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 37 ms 8404 KB Output is correct
3 Correct 11 ms 8404 KB Output is correct
4 Correct 29 ms 34004 KB Output is correct
5 Correct 26 ms 34056 KB Output is correct
6 Correct 106 ms 34036 KB Output is correct
7 Correct 18 ms 8424 KB Output is correct
8 Correct 50 ms 34004 KB Output is correct
9 Correct 49 ms 34020 KB Output is correct
10 Correct 48 ms 34048 KB Output is correct
11 Correct 64 ms 21204 KB Output is correct
12 Correct 77 ms 27632 KB Output is correct
13 Correct 80 ms 21332 KB Output is correct
14 Correct 95 ms 34040 KB Output is correct
15 Correct 106 ms 34152 KB Output is correct
16 Correct 4 ms 7400 KB Output is correct
17 Correct 4 ms 7396 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 3 ms 7380 KB Output is correct
21 Correct 4 ms 7380 KB Output is correct
22 Correct 3 ms 7380 KB Output is correct
23 Correct 4 ms 7380 KB Output is correct
24 Correct 4 ms 7380 KB Output is correct
25 Correct 3 ms 7400 KB Output is correct