oj.uz

Submission #257185

# Submission time Handle Problem Language Result Execution time Memory
257185 2020-08-03T17:17:24 Z rqi Paths (BOI18_paths) C++14
100 / 100
 879 ms 25788 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 
 
typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 
 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 
 
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
 
template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
int fstTrue(function<bool(int)> f, int lo, int hi) {
    hi ++; assert(lo <= hi); // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        int mid = (lo+hi)/2; 
        f(mid) ? hi = mid : lo = mid+1; 
    } 
    return lo;
}
 
// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
 
template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
 
template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
 
// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
template<class A> str ts(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) { 
    str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; F0R(i,SZ) res += char('0'+b[i]);
    return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
    bool fst = 1; str res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
    return "("+ts(p.f)+", "+ts(p.s)+")"; }
 
// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
    pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
    pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
 
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << ts(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
 
// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
    unsyncIO();
    // cin.exceptions(cin.failbit); 
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

const int mx = 300005;

int N, M, K;
int co[mx];
vi nodes[10];
vi curco;
ll ans;
ll num[mx];
vi adj[mx];

void search(){
	
	if(sz(curco) >= 2){
		//process
		//ps(curco);
		for(int i = 1; i <= N; i++){
			num[i] = 0;
		}

		for(auto u: nodes[curco[0]]){
			num[u] = 1;
		}
		for(int i = 0; i+1 < sz(curco); i++){
			int co1 = curco[i];
			int co2 = curco[i+1];
			for(auto x: nodes[co1]){
				for(auto y: adj[x]){
					if(co[y] != co2) continue;
					num[y]+=num[x];
				}
			}
		}
		for(auto u: nodes[curco.bk]){
			ans+=num[u];
		}
	}
	for(int i = 1; i <= K; i++){
		bool works = 1;
		for(auto u: curco){
			if(u == i){
				works = 0;
			}
		}
		if(!works) continue;
		curco.pb(i);
		search();
		curco.pop_back();
	}
}

int main() {
    setIO();
    
    cin >> N >> M >> K;
    for(int i = 1; i <= N; i++){
    	cin >> co[i];
    	nodes[co[i]].pb(i);
    }
    for(int i = 1; i <= M; i++){
    	int a, b;
    	cin >> a >> b;
    	adj[a].pb(b);
    	adj[b].pb(a);
    }
    search();

    ps(ans);
    // you should actually read the stuff at the bottom
}
 
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
*/

Compilation message

paths.cpp: In function 'void setIn(std::__cxx11::string)':
paths.cpp:128:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
paths.cpp: In function 'void setOut(std::__cxx11::string)':
paths.cpp:129:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 4 ms 7424 KB Output is correct
3 Correct 4 ms 7424 KB Output is correct
4 Correct 4 ms 7424 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 4 ms 7424 KB Output is correct
7 Correct 4 ms 7424 KB Output is correct
8 Correct 5 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 4 ms 7424 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 13944 KB Output is correct
2 Correct 73 ms 13180 KB Output is correct
3 Correct 374 ms 24952 KB Output is correct
4 Correct 99 ms 15608 KB Output is correct
5 Correct 96 ms 15388 KB Output is correct
6 Correct 235 ms 21728 KB Output is correct
7 Correct 378 ms 25000 KB Output is correct
8 Correct 414 ms 25788 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 4 ms 7424 KB Output is correct
3 Correct 4 ms 7424 KB Output is correct
4 Correct 4 ms 7424 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 4 ms 7424 KB Output is correct
7 Correct 4 ms 7424 KB Output is correct
8 Correct 5 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 4 ms 7424 KB Output is correct
11 Correct 88 ms 13944 KB Output is correct
12 Correct 73 ms 13180 KB Output is correct
13 Correct 374 ms 24952 KB Output is correct
14 Correct 99 ms 15608 KB Output is correct
15 Correct 96 ms 15388 KB Output is correct
16 Correct 235 ms 21728 KB Output is correct
17 Correct 378 ms 25000 KB Output is correct
18 Correct 414 ms 25788 KB Output is correct
19 Correct 87 ms 13944 KB Output is correct
20 Correct 86 ms 13176 KB Output is correct
21 Correct 439 ms 25064 KB Output is correct
22 Correct 103 ms 15608 KB Output is correct
23 Correct 99 ms 15352 KB Output is correct
24 Correct 245 ms 21728 KB Output is correct
25 Correct 381 ms 25064 KB Output is correct
26 Correct 369 ms 25700 KB Output is correct
27 Correct 139 ms 13180 KB Output is correct
28 Correct 166 ms 14712 KB Output is correct
29 Correct 879 ms 25000 KB Output is correct
30 Correct 487 ms 19632 KB Output is correct
31 Correct 566 ms 19564 KB Output is correct
32 Correct 872 ms 24960 KB Output is correct
33 Correct 4 ms 7424 KB Output is correct
34 Correct 4 ms 7424 KB Output is correct
35 Correct 4 ms 7424 KB Output is correct
36 Correct 4 ms 7424 KB Output is correct
37 Correct 4 ms 7424 KB Output is correct
38 Correct 4 ms 7424 KB Output is correct
39 Correct 5 ms 7424 KB Output is correct
40 Correct 5 ms 7424 KB Output is correct
41 Correct 5 ms 7424 KB Output is correct
42 Correct 4 ms 7424 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 155 ms 9336 KB Output is correct
3 Correct 38 ms 9344 KB Output is correct
4 Correct 108 ms 13164 KB Output is correct
5 Correct 82 ms 13804 KB Output is correct
6 Correct 834 ms 13284 KB Output is correct
7 Correct 47 ms 9344 KB Output is correct
8 Correct 182 ms 13208 KB Output is correct
9 Correct 135 ms 13936 KB Output is correct
10 Correct 157 ms 13916 KB Output is correct
11 Correct 380 ms 11252 KB Output is correct
12 Correct 509 ms 12656 KB Output is correct
13 Correct 384 ms 11264 KB Output is correct
14 Correct 724 ms 13284 KB Output is correct
15 Correct 726 ms 13296 KB Output is correct
16 Correct 4 ms 7424 KB Output is correct
17 Correct 4 ms 7424 KB Output is correct
18 Correct 4 ms 7424 KB Output is correct
19 Correct 5 ms 7424 KB Output is correct
20 Correct 4 ms 7424 KB Output is correct
21 Correct 5 ms 7424 KB Output is correct
22 Correct 5 ms 7424 KB Output is correct
23 Correct 5 ms 7424 KB Output is correct
24 Correct 5 ms 7424 KB Output is correct
25 Correct 4 ms 7424 KB Output is correct