Submission #1243109
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef complex<double> point; #define xx real() #define yy imag() #define REP(i, a, b) for(int i = (a); i < (int)(b); i++) #define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++) #define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++) #define SZ(x) (int)(x).size() #define BE(x) (x).begin(), (x).end() #define SORT(x) sort(BE(x)) #define _1 first #define _2 second #define x1 gray_cat_x1 #define y1 gray_cat_y1 template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } #define file "cycle" const double EPS = 1e-9; const double PI = acos(-1.); const int INF = 1e9; const ll MOD = 1e9 + 7; const int MAXN = 2e5 + 5; vi g1[MAXN], g2[MAXN]; int used1[MAXN], used2[MAXN]; int dis1[MAXN], dis2[MAXN]; int tin2[MAXN], tout2[MAXN], _t, prv2[MAXN]; bool is_prv(int a, int b){ return tin2[a] <= tin2[b] && tout2[b] <= tout2[a]; } bool check_dis_le_2(int a, int b){ if (abs(dis2[a] - dis2[b]) > 2){ return false; } if (is_prv(a, b) || is_prv(b, a)){ return true; } if (prv2[a] == prv2[b]){ return true; } return false; } int ans; int ans1; void dfs1(int s){ used1[s] = 1; ans = max(ans, 2 * dis2[s]); REP(i, 0, SZ(g1[s])){ int to = g1[s][i]; if (!used1[to]){ dis1[to] = dis1[s] + 1; if (!check_dis_le_2(s, to)){ ans1 = 1; } if (dis1[to] < dis2[to]){ dfs1(to); } } } } void dfs2(int s){ used2[s] = 1; tin2[s] = tout2[s] = _t++; REP(i, 0, SZ(g2[s])){ int to = g2[s][i]; if (!used2[to]){ prv2[to] = s; dis2[to] = dis2[s] + 1; dfs2(to); tout2[s] = tout2[to]; } } } void solve(){ int n, a, b, s1, s2; scanf("%d%d%d", &n, &s1, &s2); REP(i, 1, n){ scanf("%d%d", &a, &b); g1[a].pb(b); g1[b].pb(a); } REP(i, 1, n){ scanf("%d%d", &a, &b); g2[a].pb(b); g2[b].pb(a); } dfs2(s2); dfs1(s1); if (ans1 == 1){ ans = -1; } printf("%d\n", ans); } int main(){ //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout); int t = 1; //cin >> t; while(t--){ solve(); } }
Submission Info
Submission Time | |
---|---|
Task | E - Sugigma: The Showdown |
User | Timur_Sitdikov |
Language | C++14 (GCC 5.4.1) |
Score | 1400 |
Code Size | 2295 Byte |
Status | AC |
Exec Time | 198 ms |
Memory | 41852 KB |
Compile Error
./Main.cpp: In function ‘void solve()’: ./Main.cpp:97:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d", &n, &s1, &s2); ^ ./Main.cpp:99:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &a, &b); ^ ./Main.cpp:104:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &a, &b); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1400 / 1400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2, example3, example4 |
All | doublestar0, doublestar1, doublestar2, doublestar3, doublestar4, doublestar5, doublestar6, doublestar7, example0, example1, example2, example3, example4, giri0, giri1, giri2, giri3, giri4, giri5, giri6, giri7, giri8, giri9, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, narashi0, narashi1, narashi2, narashi3, narashi4, narashi5, narashi6, narashi7, narashi8, narashi9, ok0, ok1, ok2, ok3, ok4, ok5, ok6, ok7, ok8, ok9, ouh0, ouh1, ouh2, ouh3, ouh4, ouh5, ouh6, ouh7, ouh8, ouh9, same0, same1, same2, same3, same4, same5, same6, same7, same8, same9, sameline0, sameline1, sameline2, sameline3, sameline4, sameline5, sameline6, sameline7, sameline8, sameline9, star0, star1, star2, star3, star4, star5, star6, star7, star8, star9, supersmall0, supersmall1, supersmall2, supersmall3, supersmall4, supersmall5, supersmall6, supersmall7, supersmall8, supersmall9 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
doublestar0 | AC | 139 ms | 27896 KB |
doublestar1 | AC | 134 ms | 27256 KB |
doublestar2 | AC | 136 ms | 27768 KB |
doublestar3 | AC | 132 ms | 27128 KB |
doublestar4 | AC | 144 ms | 28152 KB |
doublestar5 | AC | 144 ms | 28280 KB |
doublestar6 | AC | 134 ms | 27128 KB |
doublestar7 | AC | 137 ms | 27256 KB |
example0 | AC | 5 ms | 13056 KB |
example1 | AC | 5 ms | 13056 KB |
example2 | AC | 5 ms | 13056 KB |
example3 | AC | 5 ms | 13056 KB |
example4 | AC | 5 ms | 13056 KB |
giri0 | AC | 160 ms | 28544 KB |
giri1 | AC | 165 ms | 27520 KB |
giri2 | AC | 163 ms | 27648 KB |
giri3 | AC | 158 ms | 27648 KB |
giri4 | AC | 164 ms | 27520 KB |
giri5 | AC | 169 ms | 28032 KB |
giri6 | AC | 165 ms | 28032 KB |
giri7 | AC | 156 ms | 27776 KB |
giri8 | AC | 164 ms | 27648 KB |
giri9 | AC | 163 ms | 27904 KB |
maxrand0 | AC | 159 ms | 28032 KB |
maxrand1 | AC | 171 ms | 27776 KB |
maxrand2 | AC | 162 ms | 28032 KB |
maxrand3 | AC | 149 ms | 27648 KB |
maxrand4 | AC | 153 ms | 27392 KB |
maxrand5 | AC | 152 ms | 27392 KB |
maxrand6 | AC | 143 ms | 27392 KB |
maxrand7 | AC | 158 ms | 27776 KB |
maxrand8 | AC | 151 ms | 27392 KB |
maxrand9 | AC | 153 ms | 27776 KB |
narashi0 | AC | 147 ms | 27136 KB |
narashi1 | AC | 160 ms | 27264 KB |
narashi2 | AC | 163 ms | 27392 KB |
narashi3 | AC | 154 ms | 27648 KB |
narashi4 | AC | 156 ms | 27648 KB |
narashi5 | AC | 158 ms | 27776 KB |
narashi6 | AC | 158 ms | 27520 KB |
narashi7 | AC | 158 ms | 28032 KB |
narashi8 | AC | 162 ms | 27776 KB |
narashi9 | AC | 149 ms | 27392 KB |
ok0 | AC | 174 ms | 39676 KB |
ok1 | AC | 174 ms | 41468 KB |
ok2 | AC | 169 ms | 36348 KB |
ok3 | AC | 171 ms | 41852 KB |
ok4 | AC | 174 ms | 33152 KB |
ok5 | AC | 174 ms | 36092 KB |
ok6 | AC | 189 ms | 37244 KB |
ok7 | AC | 198 ms | 33152 KB |
ok8 | AC | 181 ms | 39036 KB |
ok9 | AC | 162 ms | 37628 KB |
ouh0 | AC | 137 ms | 29568 KB |
ouh1 | AC | 158 ms | 30848 KB |
ouh2 | AC | 152 ms | 31744 KB |
ouh3 | AC | 153 ms | 32768 KB |
ouh4 | AC | 169 ms | 31744 KB |
ouh5 | AC | 153 ms | 38012 KB |
ouh6 | AC | 157 ms | 39676 KB |
ouh7 | AC | 155 ms | 31104 KB |
ouh8 | AC | 179 ms | 36988 KB |
ouh9 | AC | 163 ms | 39804 KB |
same0 | AC | 162 ms | 27776 KB |
same1 | AC | 156 ms | 27520 KB |
same2 | AC | 146 ms | 28032 KB |
same3 | AC | 149 ms | 27904 KB |
same4 | AC | 151 ms | 27392 KB |
same5 | AC | 178 ms | 27392 KB |
same6 | AC | 142 ms | 27648 KB |
same7 | AC | 159 ms | 27520 KB |
same8 | AC | 137 ms | 27392 KB |
same9 | AC | 166 ms | 27904 KB |
sameline0 | AC | 169 ms | 40448 KB |
sameline1 | AC | 186 ms | 40960 KB |
sameline2 | AC | 164 ms | 37120 KB |
sameline3 | AC | 164 ms | 38784 KB |
sameline4 | AC | 162 ms | 40320 KB |
sameline5 | AC | 171 ms | 40064 KB |
sameline6 | AC | 158 ms | 35584 KB |
sameline7 | AC | 190 ms | 39552 KB |
sameline8 | AC | 165 ms | 37760 KB |
sameline9 | AC | 178 ms | 35712 KB |
star0 | AC | 110 ms | 28660 KB |
star1 | AC | 107 ms | 28532 KB |
star2 | AC | 104 ms | 28660 KB |
star3 | AC | 110 ms | 28532 KB |
star4 | AC | 114 ms | 28660 KB |
star5 | AC | 119 ms | 28788 KB |
star6 | AC | 106 ms | 28788 KB |
star7 | AC | 111 ms | 28660 KB |
star8 | AC | 110 ms | 28532 KB |
star9 | AC | 116 ms | 29044 KB |
supersmall0 | AC | 5 ms | 13056 KB |
supersmall1 | AC | 5 ms | 13056 KB |
supersmall2 | AC | 5 ms | 13056 KB |
supersmall3 | AC | 5 ms | 13056 KB |
supersmall4 | AC | 5 ms | 13056 KB |
supersmall5 | AC | 5 ms | 13056 KB |
supersmall6 | AC | 5 ms | 13056 KB |
supersmall7 | AC | 5 ms | 13056 KB |
supersmall8 | AC | 5 ms | 13056 KB |
supersmall9 | AC | 5 ms | 13056 KB |