Submission #230422
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef vector<int> vi; typedef vector<vi> vii; typedef vector<string> vs; typedef vector<bool> vb; typedef vector<vb> vbb; typedef pair<int, int> pii; typedef long long ll; typedef unsigned long long ull; #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(), (a).rend() #define pb push_back #define mp make_pair #define loop(i,a,b) for(int i=(a);i<ull(b);++i) #define rep(i,n) loop(i,0,n) #define lengthof(x) (sizeof(x) / sizeof(*(x))) const double eps = 1e-10; const double pi = acos(-1.0); const double inf = (int)1e8; int V, E; map<int, vector<int> > cost; bool isFind(int s, int t){ for(int i=0; i < cost[s].size(); i++){ if(cost[s][i] == t) return true; } return false; } int dijkstra(int s, int t) { int d[100000]; bool used[100000]; fill(d, d + V, inf); fill(used, used + V, false); d[s] = 0; while(true) { int v = -1; for (int u = 0; u < V; u++) { if (!used[u] && (v == -1 || d[u] < d[v])) v = u; } if (v == -1) break; used[v] = true; for (int u = 0; u < V; u++) { int c = d[v]; if(isFind(v, u)) c+= 1; else c += inf; d[u] = min(d[u], c); } } return d[t]; } int main(){ cin >> V; E = V-1; for(int i=0; i < E; i++){ int s, t; cin >> s >> t; s--; t--; cost[s].push_back(t); cost[t].push_back(s); } int n; cin >> n; for(int i=0; i < n; i++){ int s, t; cin >> s >> t; s--; t--; cout << dijkstra(s, t)+1 << endl; } }
Submission Info
Submission Time | |
---|---|
Task | D - 閉路 |
User | LazyMii |
Language | C++ (G++ 4.6.4) |
Score | 0 |
Code Size | 1740 Byte |
Status | TLE |
Exec Time | 2038 ms |
Memory | 12456 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 30 | 0 / 70 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask1 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 | subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample01.txt | AC | 25 ms | 796 KB |
subtask0_sample02.txt | AC | 23 ms | 928 KB |
subtask0_sample03.txt | AC | 26 ms | 928 KB |
subtask1_01.txt | TLE | 2035 ms | 12224 KB |
subtask1_02.txt | TLE | 2034 ms | 12324 KB |
subtask1_03.txt | AC | 26 ms | 928 KB |
subtask1_04.txt | AC | 27 ms | 804 KB |
subtask1_05.txt | AC | 119 ms | 812 KB |
subtask1_06.txt | AC | 117 ms | 928 KB |
subtask1_07.txt | TLE | 2035 ms | 12456 KB |
subtask1_08.txt | TLE | 2035 ms | 12328 KB |
subtask1_09.txt | TLE | 2033 ms | 12324 KB |
subtask1_10.txt | TLE | 2035 ms | 12316 KB |
subtask1_11.txt | TLE | 2033 ms | 12320 KB |
subtask1_12.txt | TLE | 2033 ms | 12328 KB |
subtask2_01.txt | TLE | 2034 ms | 12328 KB |
subtask2_02.txt | TLE | 2034 ms | 12220 KB |
subtask2_03.txt | AC | 997 ms | 796 KB |
subtask2_04.txt | TLE | 2033 ms | 932 KB |
subtask2_05.txt | TLE | 2033 ms | 924 KB |
subtask2_06.txt | TLE | 2033 ms | 932 KB |
subtask2_07.txt | TLE | 2034 ms | 12456 KB |
subtask2_08.txt | TLE | 2034 ms | 12316 KB |
subtask2_09.txt | TLE | 2035 ms | 12328 KB |
subtask2_10.txt | TLE | 2038 ms | 12320 KB |
subtask2_11.txt | TLE | 2035 ms | 12320 KB |
subtask2_12.txt | TLE | 2036 ms | 12244 KB |