QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#93874#5522. F*** 3-Colorable GraphsAsad_BinWA 52ms7068kbC++173.0kb2023-04-03 15:03:232023-04-03 15:03:27

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-03 15:03:27]
  • 评测
  • 测评结果:WA
  • 用时:52ms
  • 内存:7068kb
  • [2023-04-03 15:03:23]
  • 提交

answer

// . . . Bismillahir Rahmanir Rahim . . .

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg_out cout
#define debug(...) dbg_out << "DBG )> "; __f(#__VA_ARGS__, __VA_ARGS__);
template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2> pr) { out << "{ " << pr.first << ", " << pr.second << " }"; return out; }
template<typename T1> ostream& operator<<(ostream& out, vector<T1> vec) { out << "{ "; for (auto &x: vec) out << x << ", "; out << "}"; return out; }
template<typename T1, size_t size> ostream& operator<<(ostream& out, array<T1, size> arr) { out << "{ "; for (auto &x: arr) out << x << ", "; out << "}"; return out; }
template<typename T1, typename T2> ostream& operator<<(ostream& out, map<T1, T2> mp) { out << "{ ";for (auto &x: mp) out << x.first << ": " << x.second <<  ", "; out << "}"; return out; }
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { while (isspace(name[0])) name++; (isalpha(name[0]) || name[0] == '_') ? dbg_out << name << ": " << arg1 << "\n" : dbg_out << arg1 << "\n"; dbg_out.flush();}
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) { const char *comma = strchr(names + 1, ','); while (isspace(names[0])) names++; (isalpha(names[0]) || names[0] == '_') ? dbg_out.write(names, comma - names) << ": " << arg1 << " | " : dbg_out << arg1 << " | "; __f(comma + 1, args...);}
#else
#define debug(...)
#endif

ll gcd(ll a, ll b){ while (b){ a %= b; swap(a, b);} return a;}
ll lcm(ll a, ll b){ return (a/gcd(a, b)*b);}
ll ncr(ll a, ll b){ ll x = max(a-b, b), ans=1; for(ll K=a, L=1; K>=x+1; K--, L++){ ans = ans * K; ans /= L;} return ans;}
ll bigmod(ll a,ll b,ll mod){ if(b==0){ return 1;} ll tm=bigmod(a,b/2,mod); tm=(tm*tm)%mod; if(b%2==1) tm=(tm*a)%mod; return tm;}
ll egcd(ll a,ll b,ll &x,ll &y){ if(a==0){ x=0; y=1; return b;} ll x1,y1; ll d=egcd(b%a,a,x1,y1); x=y1-(b/a)*x1; y=x1; return d;}
ll modpow(ll a,ll p,ll mod) {ll ans=1;while(p){if(p%2)ans=(ans*a)%mod;a=(a*a)%mod;p/=2;} return ans;}
ll inverse_mod(ll n,ll mod) {return modpow(n,mod-2,mod);}


const int N = 1e4;
vector<int> ara[2*N+5];
bool dp[2*N+5][4];

bool calc(int at, int p, int x, int h)
{
	if(h == 3){
		//cout << at << ' ' << h << "\n";
		for(int v : ara[at]){
			if(x == v) return true;
		}
		
		return false;
	}
	
	if(dp[at][h]) return 0;
	
	dp[at][h] = 1;
	
	//cout << at << ' ' << h << "\n";
	//cout << at << ' ' << h << "\n";
	
	bool ok = 0;
	for(auto v : ara[at]){
		if(v != p){
			ok |= calc(v, at, x, h+1);
			if(ok) return ok;
		}
	}
	
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	memset(dp, 0, sizeof dp);
	
	int n, m; cin >> n >> m;
	
	for(int K = 0; K < m; K++){
		int a, b; cin >> a >> b;
		
		ara[a].push_back(b);
		ara[b].push_back(a);
	}
	
	bool ok = 0;
	
	for(int K = 1; K <= n; K++){
		ok |= calc(K, K, K, 0);
		if(ok) break;
	}
	
	if(ok) cout << 2 << "\n";
	else cout << 3 << "\n";
	
	return 0;
}






































Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3860kb

input:

2 4
1 3
1 4
2 3
2 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3856kb

input:

3 5
1 4
2 4
2 5
3 5
3 6

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 8ms
memory: 4444kb

input:

10000 20000
4570 11730
8803 16440
4257 15381
4455 17636
5256 13543
2172 18421
7735 17847
8537 16010
6175 12263
1079 13410
335 15901
3272 16233
7435 11454
4469 13374
1564 13416
1264 13446
7484 14510
8193 12267
628 15585
1388 11398
5444 19958
2059 18140
8947 13188
6214 17707
7940 12253
6726 11508
1839...

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: -100
Wrong Answer
time: 52ms
memory: 7068kb

input:

9999 199986
8408 17344
1353 16706
3364 17274
9410 10006
9387 19375
9169 18239
3930 12759
4728 11328
5192 17935
7616 19485
3138 12714
8595 18490
6020 15039
9319 17097
7842 16814
7644 18723
2190 10117
3971 13350
232 15408
6984 12842
6988 17196
9744 18905
6759 13371
4115 18937
1842 13513
6245 18736
207...

output:

3

result:

wrong answer 1st numbers differ - expected: '2', found: '3'