Submission #2121599
Source Code Expand
#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define N 200005
#define LOGN 20
using namespace std;
struct Edge{
int u, v, w;
Edge(int _u, int _v, int _w){ u = _u; v = _v; w = _w; }
Edge(){}
void read(){ scanf("%d%d", &u, &v); u--; v--; }
void print(){ printf("%d %d %d\n", u, v, w); }
};
Edge E[N];
bool operator <(const Edge &e1, const Edge &e2){ return e1.w < e2.w; }
int P[N], size[N], heavyEdge[N], n, m, nodes;
int Find(int x){
if(x == P[x])return x;
return P[x] = Find(P[x]);
}
void Union(int x, int y){ //First one will be the superset any time
x = Find(x);
y = Find(y);
P[y] = x;
size[x] += size[y];
}
vector<Edge> GetMinimumSpanningTree(){
vector<Edge>ans;
int u, v, w;
for(int i = 0; i < n; i++)P[i] = i;
//sort(E, E + m);
for(int i = 0; i < m; i++){
u = E[i].u;
v = E[i].v;
w = E[i].w;
if(Find(u) != Find(v))Union(u, v), ans.pb(E[i]);
}
return ans;
}
int Next[LOGN][N];
int Explore(int u, int v, int heaviest){
int supersetSize = 0;
for(int i = LOGN - 1; i >= 0; i--){
if(Next[i][u] == -1 || heavyEdge[Next[i][u]] > heaviest)continue;
u = Next[i][u];
}
supersetSize += size[u];
for(int i = LOGN - 1; i >= 0; i--){
if(Next[i][v] == -1 || heavyEdge[Next[i][v]] > heaviest)continue;
v = Next[i][v];
}
if(u != v)supersetSize += size[v];
return supersetSize;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)E[i].read(), E[i].w = i + 1;
vector<Edge>MST = GetMinimumSpanningTree();
//for(int i = 0; i < n - 1; i++)MST[i].print();
nodes = n;
for(int i = 0; i < n; i++)P[i] = i, size[i] = 1;
for(int i = n; i < 2 * n; i++)P[i] = i, size[i] = 0;
int u, v, w;
memset(Next, -1, sizeof Next);
for(int i = 0; i < MST.size(); i++){
u = MST[i].u;
v = MST[i].v;
w = MST[i].w;
Next[0][Find(u)] = nodes;
Next[0][Find(v)] = nodes;
Union(nodes, Find(u));
Union(nodes, Find(v));
heavyEdge[nodes] = w;
nodes++;
}
//for(int i = 0; i < nodes; i++)printf("node: %d | parent: %d | size: %d | heavyEdge: %d\n", i, Next[0][i], size[i], heavyEdge[i]);
for(int j = 1; j < LOGN; j++){
for(int i = 0; i < nodes; i++){
if(Next[j - 1][i] == -1)continue;
Next[j][i] = Next[j - 1][Next[j - 1][i]];
}
}
int q, z;
scanf("%d", &q);
for(int i = 0; i < q; i++){
scanf("%d%d%d", &u, &v, &z);
u--; v--;
int lo = 1, hi = m, me;
while(lo < hi){
me = lo + (hi - lo)/2;
if(Explore(u, v, me) >= z)hi = me;
else lo = me + 1;
}
printf("%d\n", lo);
}
}
Submission Info
Submission Time |
|
Task |
A - Range Product |
User |
Woreviam |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2740 Byte |
Status |
RE |
Exec Time |
173 ms |
Memory |
18688 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:82:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
./Main.cpp:124:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
./Main.cpp:128:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &z);
^
./Main.cpp: In member function ‘void Edge::read()’:
./Main.cpp:15:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void read(){ scanf("%d%d", &u, &v); u--; v--; }
^
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
0 / 100 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
Subtask1 |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
WA |
6 ms |
18688 KB |
0_01.txt |
WA |
6 ms |
16640 KB |
0_02.txt |
WA |
6 ms |
18688 KB |
1_00.txt |
WA |
6 ms |
18688 KB |
1_01.txt |
WA |
6 ms |
16640 KB |
1_02.txt |
WA |
6 ms |
16640 KB |
1_03.txt |
WA |
6 ms |
18688 KB |
2_00.txt |
RE |
173 ms |
6272 KB |
2_01.txt |
WA |
6 ms |
16640 KB |
2_02.txt |
WA |
6 ms |
16640 KB |
2_03.txt |
RE |
172 ms |
6272 KB |